patternMinor
Finding the maximum bandwidth along a single path in a network
Viewed 0 times
paththemaximumnetworksinglefindingbandwidthalong
Problem
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?
Solution
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(m^2)$, 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.
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(m^2)$, 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.
Context
StackExchange Computer Science Q#1591, answer score: 5
Revisions (0)
No revisions yet.