Computer Science > Solutions Guide > SUNY Buffalo State College CSE 531a5-sol (All)
Solution to CSE 531 Homework Assignment 5 Prepared by Hung Q. Ngo∗ November 22, 2007 Problem 1. We define the Escape Problem as follows. We are given a directed graph G = (V, E) (picture a netwo... rk of roads). A certain collection of nodes X ⊂ V are designated as populated nodes, and a certain other collection S ⊂ V are designated as safe nodes. (Assume that X and S are disjoint.) In case of an emergency, we want evacuation routes from the populated nodes to the safe nodes. A set of evacuation routes is defined as a set of paths in G so that (i) each node in X is the starting point of one path, (ii) the last node on each path lies in S, and (iii) the paths do not share any edges. Such a set of paths gives a way for the occupants of the populated nodes to “escape” to S, without overly congesting any edge in G. (a) Given G, X, and S, show how to decide in polynomial time whether such a set of evacuation routes exists. (b) Suppose we have exactly the same problem as in (a), but we want to enforce an even stronger version of the “no congestion” condition (iii): we change (iii) to say “the paths do not share any nodes.” With this new condition, show how to decide in polynomial time whether such a set of evacuation routes exists. (c) Provide an example with the same G, X, and S, in which the answer is yes to the question in (a) but no to the question in (b). Solution Sketch. (a) Construct a flow network D as shown in Figure 1. All edge capacities are set to 1. Only the edges from S to t are of capacities |X| [Show More]
Last updated: 1 year ago
Preview 1 out of 8 pages
Connected school, study & course
About the document
Uploaded On
Jul 08, 2021
Number of pages
8
Written in
This document has been written for:
Uploaded
Jul 08, 2021
Downloads
0
Views
156
In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.
We're available through e-mail, Twitter, Facebook, and live chat.
FAQ
Questions? Leave a message!
Copyright © Browsegrades · High quality services·