Suppose you are given a network, G, of routers (vertices) and links (edges), wit

Question

Suppose you are given a network, G, of routers (vertices) and links (edges), with a source, s, and sink, t, together with bandwidth constraints on each edge, which indicate the maximum speed MB/s that the communication link represented by that edge can support. As in a Maximum Flow Algorithm, your goal is to produce a maximum flow from s to t, respecting the bandwidth constraints on the edges. Suppose now, however, that you also have a bandwidth constraint on each router in the network, which specifies the maximum amount of information MB/s that can pass through that router. Describe an efficient algorithm for finding a maximum flow in the network, G, that satisfies the bandwidth capacity constraints on the edges as well as the vertices. What is the running time of your algorithm?

Explanation / Answer

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

•Augmentation can be done in O(E).

•Total worst-case running time O(E|f*|), where f* is the max-flow found by the algorithm.If all flows are integers, then the while loop of Ford-Fulkerson is run at most  times, where  is the maximum flow. This is because the flow is increased, at worst, by 1 in each iteration.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.