Algorithm Design Chapter 7 Question 23

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, som some nodes are in the middle. However, G can have many minimum cuts, so we have to be e nodes are clearly on the "sink side" of the main bottlenecks; and ul 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 e A-that is, v lies on B),we have ve 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 ve B-that is, v lies the sink side of every minimum cut We say a node v is central if it is neitheru minimum s-t cut (A, B) for which v e A, and at least one minimum s-t cut (A1, B') for which v e 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. on is central if it is neither upstream nor downstream; there is at least one