Summary
A new algorithm for finding a maximal flow in a given network is presented. The algorithm runs in time O(V ^{5/3} E ^{2/3}), where V and E are the number of the vertices and edges in the network.
This is a preview of subscription content, access via your institution.
Abbreviations
 balance a vertex υ :

reduce the flow in in (υ) until υ is balanced
 balanced vertex:

a vertex υ with excess (υ) = 0
 big edge:

an edge in FOREST which represents an open path in SL _{ i }
 c(e):

the capacity of a (small) edge in the layered network
 c(ê):

the capacity of a big edge ê, which equals the minimal residual capacity of a small edge on the corresponding path
 closed edge:

an edge that has been closed by the algorithm either because it became saturated or because it led to a closed vertex
 closed vertex:

a vertex υ, υ ≠ t, such that all edges in out (υ) are closed
 degree(\(\hat \upsilon \)):

the number of big edges entering a junction \(\hat \upsilon \)
 Δ(υ):

a doubly linked list containing all edges e in in(υ) with newflow (e)>0
 excess(υ):

\(\sum\limits_{e \in in(\upsilon )} {f(e)  } \sum\limits_{e \in out(\upsilon )} {f(e)} \)
 excess (\(\hat \upsilon \)):

the sum of newflow (ê) for ê in LIST (\(\hat \upsilon \)) minus newflow of the big edge that leaves \(\hat \upsilon \). (The corresponding term for êoldflow's is zero)
 f(e):

the flow in the edge e
 front layer of SL _{ i } :

the layer in SL _{ i }closest to t
 in(υ):

the list of edges that enter υ in the layered network
 junction:

a vertex in FOREST_{ i }
 ℓ _{ i } :

the number of the calls to PUSH(i)
 LIST(ê):

the list of the small edges on the path corresponding to a big edge ê
 LIST(û):

the list of the big edges entering a junction û
 list_{ j } :

the list of big edges in FOREST_{ i } which start at V _{ j }
 m :

the number of special vertices
 m _{ i } :

the number of vertices in the rear layer of SL _{ i }
 marked vertex:

a vertex on a path that corresponds to a big edge
 micropush:

a push of flow from a microsource
 microsource:

an open vertex that becomes positive during BALANCE(i)
 newflow(e):

the total flow increment in a (small) edge e = (u, υ) in SL _{ i }since the last call to PUSH (i), that pushed flow into υ
 newflow (ê):

the total flow increment in a big edge ê in FOREST_{ i } since the last call to PUSH(i)
 open edge:

an edge that has not been closed by the algorithm; an open edge cannot be saturated and cannot lead to a closed vertex
 open vertex υ :

a vertex υ such that either υ = t or there are open edges in out(υ)
 open path:

a path consisting of open edges and open vertices
 out(υ):

the list of edges that leave υ in the layered network
 positive vertex:

a vertex υ, υ ≠ t, with excess (υ)>0
 pushnumber(υ):

the number of the last PUSH(i) that pushed flow into υ
 rear layer of SL _{ i } :

the layer in SL _{ i }closest to s. Its vertices belong to SL _{ i } −1
 saturated edge:

an edge e with f(e) = c(e)
 SL _{ i } :

the ith superlayer
 small edge:

an edge in the layered network
 special vertex:

a vertex in a special layer
 special layer:

a layer chosen by the algorithm as special
 superlayer:

the part of the layered network between two consecutive special layers
 totalflow(e):

f(e) + oldflow (ê) + newflow (ê), if e ε LIST (ê) and f(e) otherwise
 verynewflow(e):

part of newflow (ê) used for balancing junctions; modified like newflow (ê) except for the case when it is set to zero when a big edge below it is deleted
 V _{ p } :

the rear layer of SL _{ i }
 V _{ q } :

the front layer of SL _{ i }
 x :

the bound on the number of layers in a superlayer
References
 1.
AdelsonVelsky GM, Dinic EA, Karzanov AV (1975) Flow algorithms, (in Russian). Nauka, Moscow
 2.
Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Reading, Mass AddisonWesley
 3.
Cherkasky BV (1977) Algorithm of construction of maximal flow in networks with complexity of O(V ^{√} E) operations (in Russian). Mathematical Methods of Solution of Economical Problems 7: 117–125
 4.
Dinic EA (1970) Algorithm for solution of a problem of maximal flow in a network with power estimation. Soviet Math Dokl 11: 1277–1280
 5.
Edmonds J, Karp RM (1972) Theoretical improvement in algorithmic efficiency for network flow problems. JCAM 19: 248–264
 6.
Even S (1976) The maxflow algorithm of Dinic and Karzanov: An exposition, MIT, LCS, TM80
 7.
Ford LR, Fulkerson DR (1962) Flows in networks. Princeton University Press, New Jersey
 8.
Ford LR, Fulkerson DR (1956) Maximal flows through a network. IRE Trans on Inform Theory, IT2:117–119
 9.
Galil Z (1980) On the theoretical efficiency of various network flow algorithms. IBM Report, RC7320, September 1978, Theor Comput Sci (in press)
 10.
Galil Z, Naamad A (1980) Network flow and generalized path compression. Proceedings 11th Annual ACM Symposium on Theory of Computing, May 1979, 13–26. To appear in J Comput System Sci as: An O(EVlog^{2} V) algorithm for the maximal flow problem
 11.
Karzanov AV (1974) Determining the maximal flow in a network by the method of preflows. Soviet Math Dokl 15:434–437
 12.
Knuth DE (1968) The art of computer programming. Vol 1 (Fundamental algorithms). AddisonWesley Reading, Mass
 13.
Malhotra VM, Pramodh Kumar M, Maheshwary SN (1978) An O(V ^{3}) algorithm for finding the maximal flow in networks. Information Processing Lett 7:277–278
Author information
Affiliations
Additional information
We use the notation A = 0(B) [A = Ω(B)] for A ≦ cB [A ≧ cB], and A = θ(B) for c _{1} B≦A ≦ c _{2} B where c, c _{1}and c _{2}are positive constants. (The same constants for all the occurrences of this notation)
Rights and permissions
About this article
Cite this article
Galil, Z. An O(V ^{5/3} E ^{2/3}) algorithm for the maximal flow problem. Acta Informatica 14, 221–242 (1980). https://doi.org/10.1007/BF00264254
Received:
Revised:
Issue Date:
Keywords
 Information System
 Operating System
 Data Structure
 Communication Network
 Information Theory