Suppose you’re looking at a flow network G with source s and sink t, and you wan
ID: 3762779 • Letter: S
Question
Suppose you’re looking at a flow network G with source s and sink t, and you want to be able to express something like the following intuitive notion: Some nodes are clearly on the “source side” of the main bottlenecks; some nodes are clearly on the “sink side” of the main bottlenecks; and some nodes are in the middle. However, G can have many minimum cuts, so we have to be careful in how we try making this idea precise.Here’s one way to divide the nodes of G into three categories of this sort. . We say a node v is upstream if, for all minimum s-t cuts (A, B), we have v A—that is, v lies on the source side of every minimum cut. . We say a node v is downstream if, for all minimum s-t cuts (A, B), we have v B—that is, v lies on the sink side of every minimum cut. . We say a node v is central if it is neither upstream nor downstream; there is at least one minimum s-t cut (A, B) for which v A, and at least one minimum s-t cut (A, B) for which v B. Give an algorithm that takes a flow network G and classifies each of its nodes as being upstream, downstream, or central. The running time of your algorithm should be within a constant factor of the time required to compute a single maximum flow.
Explanation / Answer
https://cgi.csc.liv.ac.uk/~martin/teaching/comp202/Exercises/Maximum-flow-solution.pdf
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.