File MaxFlow.h

↰ Parent directory (ADS/graph)

The maximum flow of section 15.2 in a network G = ( V , E , s , t , c ), with integer capacities, and the minimum cut.

Definition (ADS/graph/MaxFlow.h)

Detailed Description

The network keeps for each edge its residual twin, so that the residual capacity :math:` c_f( u , v ) = c( u , v ) - f( u , v ) ` of both directions is at hand. By the Teorema 15.1 (maximum flow / minimum cut) f is maximum if and only if there is no augmenting path, a path from s to t in the residual network, and then the nodes S reached from s give a cut ( S , V - S ) of capacity |f|. The local search augments the flow along augmenting paths:

  • FORD_FULKERSON, any path, by a depth first visit: O( ( n + m ) |f*| );

  • EDMONDS_KARP, a shortest path, by a breadth first visit: O( n m^2 );

  • DINIC, the blocking flows of the levels of a breadth first visit: :math:` O( n^2 m ) , and :math: O( m sqrt{n} ) ` with unit capacities, e.g., the bipartite matching (the bound that the book gives for the algorithm of the three Indians, Karzanov, Malhotra, Kumar and Maheshwari, of which this is the forerunner).

The best bound that the book attributes to Karmarkar (1984), :math:` O( n m log( n^2 / m ) ) `, is the one of the push-relabel of Goldberg and Tarjan (1988); Karmarkar’s is the interior point method for linear programming. feasibleCirculation() decides whether a circulation with lower and upper bounds on the edges exists, by a maximum flow from a new source that gives each node the lower bounds entering it.

The contracts [see File Contract.h]: a network has n >= 0 nodes, an edge joins two of them with a capacity c >= 0, maxFlow() needs two distinct nodes; the invariant is the skew symmetry of the flow on each edge and its twin, within the capacity. At the level of the audits maxFlow() ensures that no augmenting path is left, and feasibleCirculation() that the flows it gives are within the bounds and conserved at every node. The operations are defined in MaxFlow.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 15.2, https://algoritmicamente.it/materiali/libro/capitoli/cap15.pdf

    1. Ford, D. R. Fulkerson, Maximal flow through a network, Canadian Journal of Mathematics 8, 399-404, 1956, doi:10.4153/CJM-1956-045-5

  1. Edmonds, R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM 19(2), 248-264, 1972, doi:10.1145/321694.321699

    1. Dinic, Algorithm for solution of a problem of maximum flow in a network with power estimation, Soviet Mathematics Doklady 11, 1277-1280, 1970

    1. Karzanov, Determining the maximal flow in a network by the method of preflows, Soviet Mathematics Doklady 15, 434-437, 1974

    1. Malhotra, M. P. Kumar, S. N. Maheshwari, An O( |V|^3 ) algorithm for finding maximum flows in networks, Information Processing Letters 7(6), 277-278, 1978, doi:10.1016/0020-0190(78)90016-9

  1. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4(4), 373-395, 1984, doi:10.1007/BF02579150

    1. Goldberg, R. E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM 35(4), 921-940, 1988, doi:10.1145/48014.61051

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Enums

Functions