I am trying to search for an algorithm that can tell me which node has the highe

Question

I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link bandwidths. I have looked at the maximal flow problem and at the Edmond-Karp algorithm. My questions are the following:

Edmond-Karp just tells us how much throughput we can get (at the sink) from source to sink if any of the paths were used. Correct?
Edmond-Karp does not tell us which path can give us the maximum flow. Correct?

Explanation / Answer

A very simple approach for question 2 is the following. Sort the edges by capacity. Remove the edge with lowest capacity, and check if there is still a path from s to t. If there is, move on the edge with the second lowest capacity, and so on.

At some point, we will disconnect s from t by removing an edge of capacity c. Now, we know that c is the maximum capacity of a single path from s to t.

This algorithm takes time O(m2), since the connectivity check can be made in time O(m), and we can remove each edge at most once.

Now you can find the actual path (there might be many) of maximum capacity, by finding any s-t path in this reduced graph.

When considering node-capacity, remember to change your graph to support that.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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