Reputation: 65
can we find an algorithm which computes (in linear-time) the maximum flow for tree-like networks, that is, for networks such that the removal of the sink (and its associated edges) leaves a tree.
Upvotes: 0
Views: 870
Reputation: 23643
Yes, just run something like the following:
maxf(s) {
if (s == sink) return s.in_capacity;
ret = 0;
foreach(c in children(s)) ret += maxf(c);
return min(ret, s.in_capacity);
}
Use an initial call with s equal to the source (we assume that the source has an in_capacity of infinity).
Upvotes: 2
Reputation: 1497
Ford-Fulkerson is O(E*f) where E is the number of edges and f the maximum flow, which would be considered linear if you have a constant upper bound on E or f in your problem.
Upvotes: 0