How to define the Escape Problem

Assignment Help Computer Engineering
Reference no: EM133399

Question

We define the Escape Problem as follows. We are given a directed graph G = (V; E) (picture a network of roads.) A sure collection of vertices X V is designated as populated vertices and a positive other collection S V is designated as safe vertices. (Assume that X and S are disjoint.) In case of an emergency, we want migration routes from the populated vertices to the safe vertices. A set of evacuation routes is de?ned as a set of paths in G such that

(i) each vertex in X is the tail of one path,

(ii) the last vertex on each path lies in S, and

(iii) The paths do not share any edges. Such a set of paths gives way for occupants of the populated vertices to "escape" to S without overly congesting any edge in G.

(a) Given G, X, and S, shows how to decide in polynomial time whether such a set of evacuation routes exists.

(b) Assume we have exactly the same problem as in (a), but we want to enforce an even stronger version of the "no congestion" condition (iii). Thus we change (iii) to say, "The paths do not share any vertices." With this new state, show how to decide in polynomial time whether such a set of evacuation routes exists. Also provide an instance with the same G, X, and S in that the answer is "yes" to the question in (a) but "no" to the question in (b).

Reference no: EM133399

Questions Cloud

Distinguish between functional value and emotional value : Distinguish between functional value and emotional value. Illustrate with examples. (b) Discuss the importance of functional and emotional value in the creation of genuine customer relationships
Risk in the audit plan : Classify the main account or group of accounts affected by this risk in the audit plan.
Market segmentation : arket segmentation, consumer decision-making process, tourism and hospitality marketing, marketing research tool
Management accounting formats : Management accounting formats are identical for all companies
How to define the Escape Problem : How to  define the Escape Problem
Determine and journalize the foreign exchange adjustments : Determine and journalize the foreign exchange adjustments for 2005, 2006 and 2007 for the Canadian subsidiary.
How would you propose the update to star topology : How would you propose the update to Star topology
What is the partnerships basis in the assets contributed : How much is recognized profit? How much is each partner's basis in the partnership? What is the partnership's basis in the assets contributed?
Demand and capacity : Process Layout, Product Layout, Fixed position Layout, shaping of business policy, key objective of the operations manager, managing both demand and capacity

Reviews

Write a Review

 

Computer Engineering Questions & Answers

  Propose a wiring plan for network servers

Propose a wiring plan for network servers.

  Define role of customer and end-user on an agile process

Define role of customer and end-user on an agile process

  Findout which statement provide required output

Findout which statement provide required output

  Problem on troubleshooting dns records

Problem on Troubleshooting DNS Records

  Ict governance

ICT is defined as the term of Information and communication technologies, it is diverse set of technical tools and resources used by the government agencies to communicate and produce, circulate, store, and manage all information.

  Calculate yield to maturity and bond prices

Calculate yield to maturity (YTM) and bond prices

  Predicate color and action paint using situation calculus

Predicate color and action paint using situation calculus

  Examine the behavior of airfoil

Write HW assignment written in Matlab airfoils have different C mc/4

  Java program that asks the user to enter two numbers x and b

Java program that asks the user to enter two numbers x and b.

  Program on string representing

Program on  string representing

  How to suggest a solution for the scenario of warehouse

How to Suggest a solution for the scenario of warehouse? Assume that the company has accumulated 20TB of data and that 20 percent per year growth is expected in size of Data Warehouse. Suggest a solution for this scenario with respect to software,..

  Problem on sql statement

Problem on  SQL statement

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd