×
Galil, Zvi; Naamad, Amnon

An \(O(EV\log^2V)\) algorithm for the maximal flow problem. (English) Zbl 0449.90094

J. Comput. Syst. Sci. 21, 203-217 (1980).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0449.90094

Cited in 13 Documents

MSC:

90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
90B10 Deterministic network models in operations research
68Q25 Analysis of algorithms and problem complexity
68Q60 Specification and verification (program logics, model checking, etc.)

Keywords:

maximal flow problem; path compression; union find algorithm; flows in networks; comparison of algorithms; numerical analysis; implementation; asymptotic behavior
PDF BibTeX XML Cite
\textit{Z. Galil} and \textit{A. Naamad}, J. Comput. Syst. Sci. 21, 203--217 (1980; Zbl 0449.90094)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[2] Berge, C.; Ghouila-Houri, A., Programming, games and transportation networks, (1965), Methuen London
[3] Cherkasky, B.V., Algorithm of construction of maximal flow in networks with complexity of O(V2 √E) operations, Math. meth. solution econ. prob., 7, 117-125, (1977), (in Russian)
[4] Dinic, E.A., Algorithm for solution of a problem of maximal flow in a network with power estimation, Soviet math. dokl., 11, 1277-1280, (1970) · Zbl 0219.90046
[5] Edmonds, J.; Karp, R.M., Theoretical improvement in algorithmic efficiency for network flow problems, J. assoc. comput. Mach., 19, 2, 248-264, (1972) · Zbl 0318.90024
[6] Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton Univ. Press Princeton, N. J · Zbl 0139.13701
[7] Ford, L.R.; Fulkerson, D.R., Maximal flows through a network, I.E.E.E. trans. inform. theory, IT-2, 117-119, (1956) · Zbl 0073.40203
[8] Ford, L.R.; Fulkerson, D.R., Maximal flow through a network, Canad. J. math., 8, 399-404, (1956) · Zbl 0073.40203
[9] Galil, Z., A new algorithm for the maximal flow problem, (), 231-245
[10] to appear as An \(O(E\^{}\{23\}V\^{}\{53\})\) algorithm for the maximal flow problem, Acta Inform., in press.
[11] {\scZ. Galil and A. Naamad}, unpublished manuscript, August 1978.
[12] Galil, Z., On the theoretical efficiency of various network flow algorithms, IBM report, RC7320, (September 1978)
[13] Theoret. Comput. Sci., in press.
[14] Itai, A.; Shiloach, Y., Maximum flow in planar graphs, SIAM comput., 8, 2, 135-150, (1979) · Zbl 0419.90040
[15] Karzanov, A.V., Determining the maximal flow in a network by the method of preflows, Soviet math. dokl., 15, 434-437, (1974) · Zbl 0303.90014
[16] Malhotra, V.M.; Pramodh Kumar, M.; Maheshwari, S.N., An O(V3) algorithm for finding the maximum flows in networks, (), 277-278, 6 · Zbl 0391.90041
[17] {\scM. Paterson}, unpublished (see [17]).
[18] Shiloach, Y., An O(ni log2I) maximum-flow algorithm, Stanford technical report STAN-CS-78-702, (December 1978)
[19] Tarjan, R.E., Efficiency of a good but not linear set union algorithm, J. assoc. comput.Mach., 22, 2, 215-225, (1975) · Zbl 0307.68029
[20] {\scD. D. Sleator}, An O(mn log m) algorithm for maximum network flow, Ph.D. thesis, Stanford University, to appear.
[21] Bent, S.W.; Sleator, D.D.; Tarjan, R.E., Biased 2-3 trees, (), 248-253
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.