Menu
Will the Ford-Fulkerson algorithm find a maximum flow of a unit-capacity flow network (all edges have unit capacity) with n vertices and m edges in O(mn) time?
492
Running time of Ford-Fulkerson Each iteration of Ford-Fulkerson takes O(E) time to find an augmenting path (Gf has at least E and at most 2E edges, so the time is O(V+2E) = O(E+E) = O(E)). Each iteration also increases the flow by at least 1, assuming all capacities are integers.
Ford-Fulkerson algorithm is a greedy approach for calculating the maximum possible flow in a network or a graph. A term, flow network, is used to describe a network of vertices and edges with a source (S) and a sink (T). Each vertex, except S and T, can receive and send an equal amount of stuff through it.
For instance, the basic Ford- Fulkerson algorithm is not a polynomial-time algorithm for network flow when edge capacities are written in binary, but both of the Edmonds-Karp algorithms are polynomial-time.
O(M*f) is a known running time estimation for Ford-Fulkerson on graphs with integer capacities, where M is the number of edges and f the value of maximal flow, just because it is easy to find augmenting paths in O(M) each, and each such path increases the flow by at least 1.
If your graph has no duplicate edges (that is, there is no pair of edges that has the same start and end vertices), and each edge has unit capacity, then the the maximal flow f is no more than the number of vertices N (just because there is no more than N-1 edges going from the source), and therefore the complexity is indeed O(N*M).
However, if your graph is allowed to have duplicate edges (but still each edge has capacity of 1), then f can be bigger than N, and up to M, and the time complexity can become O(M*M), and it is not difficult to come with an example where such complexity takes place.
57
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
