CODEWITHSUNDEEP
algorithmnetwork-programmingmaxgraph-algorithm
conapart
conapart

Reputation: 65

Compute Max flow for networks

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

Answers (2)

jonderry
jonderry

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

xyz
xyz

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

Related Questions