Solutions
We can define the Residual Graph, which provides a systematic way to search for forward-backward operations in order to find the maximum flow.
Given a flow network, and a flow on, we define the residual graph of with respect to as follows.
1. The node set of is the same as that of .
2. Each edge of is with a capacity of .
3. Each edge of is with a capacity of .
The following table lists algorithms for solving the maximum flow problem.
| Method | Complexity | Description |
|---|---|---|
| Linear programming | Constraints given by the definition of a legal flow. See the linear program here. | |
| Ford–Fulkerson algorithm | O(E max| f |) | As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path.
The algorithm works only if all weights are integers. Otherwise it is possible that the Ford–Fulkerson algorithm will not converge to the maximum value. |
| Edmonds–Karp algorithm | O(VE2) | A specialization of Ford–Fulkerson, finding augmenting paths with breadth-first search. |
| Dinitz blocking flow algorithm | O(V2E) | In each phase the algorithms builds a layered graph with breadth-first search on the residual graph. The maximum flow in a layered graph can be calculated in O(VE) time, and the maximum number of the phases is n-1. In networks with unit capacities, Dinic's algorithm terminates in time. |
| General push-relabel maximum flow algorithm | O(V2E) | The push relabel algorithm maintains a preflow, i.e. a flow function with the possibility of excess in the vertices. The algorithm runs while there is a vertex with positive excess, i.e. an active vertex in the graph. The push operation increases the flow on a residual edge, and a height function on the vertices controls which residual edges can be pushed. The height function is changed with a relabel operation. The proper definitions of these operations guarantee that the resulting flow function is a maximum flow. |
| Push-relabel algorithm with FIFO vertex selection rule | O(V3) | Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations until the excess is positive or there are admissible residual edges from this vertex. |
| Dinitz blocking flow algorithm with dynamic trees | O(VE log(V)) | The dynamic trees data structure speeds up the maximum flow computation in the layered graph to O(Elog(V)). |
| Push-relabel algorithm with dynamic trees | O(VE log(V2/E)) | The algorithm builds limited size trees on the residual graph regarding to height function. These trees provide multilevel push operations. |
| Binary blocking flow algorithm | The value U corresponds to the maximum capacity of the network. | |
| MPM (Malhotra, Pramodh-Kumar and Maheshwari) algorithm | O(V3) | |
| Jim Orlin's + KRT (King, Rao, Tarjan)'s algorithm | O(VE) | Orlin's algorithm solves max-flow in O(VE) time for while KRT solve it in O(VE) for |
For a more extensive list, see .
Read more about this topic: Maximum Flow Problem
Famous quotes containing the word solutions:
“Science fiction writers foresee the inevitable, and although problems and catastrophes may be inevitable, solutions are not.”
—Isaac Asimov (1920–1992)
“Those great ideas which come to you in your sleep just before you awake in morning, those solutions to the world’s problems which, in the light of day, turn out to be duds of the puniest order, couldn’t they be put to some use, after all?”
—Robert Benchley (1889–1945)
“The anorexic prefigures this culture in rather a poetic fashion by trying to keep it at bay. He refuses lack. He says: I lack nothing, therefore I shall not eat. With the overweight person, it is the opposite: he refuses fullness, repletion. He says, I lack everything, so I will eat anything at all. The anorexic staves off lack by emptiness, the overweight person staves off fullness by excess. Both are homeopathic final solutions, solutions by extermination.”
—Jean Baudrillard (b. 1929)