Computational Maximum Flow Bibliography
We present two lists. The first one
contains experimental papers on maximum flow algorithms,
in chronological order.
The second list contains papers introducing algorithmic techniques for
solving maximum flow problems.
This list is organized by topics, and restricted to original papers
and fundamental techniques.
When a paper has several versions,
we list the most current version. We list other versions only for a good
reason: e.g. if the journal version of a paper contains only partial
data, we also list a technical report with complete data.
Computational Papers
-
A Fast Algorithm for Computing Maximum Flow in a Network,
B.V. Cherkassky,
in Collected Papers, Vol. 3,
Institute for Systems Studies, Moscow, 23-30, 1979.
-
Efficient Graph Algorithms for Sequential and Parallel Computers,
A. V. Goldberg,
PdD thesis, MIT, 1987.
Also available as Technical Report TR-374, Laboratory for Computer Science,
MIT, 1987.
-
A Computational Comparison of the Dinic and Network Simplex
Methods for Maximum Flow,
D. Goldfarb and M. D. Grigoriadis,
Annals of Oper. Res. (13) 83-123, 1988.
-
Implementing Goldberg's Max-Flow Algorithm - A Computational
Investigation,
U. Derigs and W. Meier,
ZOR - Methods and Models of Operations Research (33) 383-403,
1989.
-
Goldrmf/Goldnet-max-flow Program,
U. Derigs and W. Meier,
Europ. J. Oper. Res. (46) 260,
1990.
-
An Evaluation of Algorithmic Refinements and Proper Data-Structures
for the Preflow-Push Approach for Maximum Flow,
U. Derigs and W. Meier,
ASI Series on Computer and System Sciences, (8), 209-223,
NATO, 1992.
-
On the Parallel Implementation of Goldberg's Maximum Flow
Algorithm,
R. J. Anderson and J. C. Setubal,
in proc. of the 4th Annual ACM Symp. on Parallel Algo. and Arch.,
168-177, ACM 1992.
-
Goldberg's Algorithm for the Maximum Flow in Perspective:
a Computational Study,
R. J. Anderson and J. C. Setubal,
in Network Flows and Matching: First DIMACS Implementation
Challenge, refereed proceedings, D. S. Johnson and C. C. McGeoch
(editors), 1-18, AMS, 1993.
-
Implementations of Goldberg-Tarjan Maximum Flow Algorithm,
Q. C. Nguyen and V. Venkateswaran,
in Network Flows and Matching: First DIMACS Implementation
Challenge, refereed proceedings, D. S. Johnson and C. C. McGeoch
(editors), 19-42, AMS, 1993.
-
Implementing the Push-Relabel Method for the Maximum Flow
Problem on the Connection Machine,
F. Alizadeh and A. V. Goldberg,
in Network Flows and Matching: First DIMACS Implementation
Challenge, refereed proceedings, D. S. Johnson and C. C. McGeoch
(editors), 65-96, AMS, 1993.
-
On Implementing Push-Relabel Method for the Maximum Flow Problem,
B. V. Cherkassky and A.V. Goldberg,
Algorithmica (19), 390-410, 1997.
-
An Implementation of the Binary Blocking Flow Algorithm,
T. Hagerup, P. Sanders, and J. L. Traeff,
Proceedings of the 2-nd Workshop on Algorithm Engineering ,
143-154, K. Mehlhorn, editor, Saarbruken, Germany, 1998. Available at
http://www.mpi-sb.mpg.de/~wae98/PROCEEDINGS/
Basic Techniques
Augmenting paths
Maximal Flow Through a Network,
L. R. Ford, Jr. and D. R. Fulkerson,
Canadian Journal of Math. (8), 399-404, 1956.
Blocking flows
Algorithm for Solution of a Problem of Maximum Flow in
Networks with Power Estimation,
E. A. Dinic,
Soviet Math. Dokl., (11) 1277-1280, 1970.
Determining the Maximal Flow in a Network by the Method of
Preflows,
A. V. Karzanov,
Soviet Math. Dokl., (15) 434-437, 1974.
The above paper also introduces preflows and the push operation.
Push-relabel method
A New Approach to the Maximum Flow Problem,
A. V. Goldberg and R. E. Tarjan,
JACM (35), 921-940, 1988.
Scaling
Metod Porazryadnogo Sokrashcheniya Nevyazok i Transportnye
Zadachi,
E. A. Dinic,
in Issledovaniya po Diskretnoi Matematike,
Nauka, Moscow, 1973.
In Russian, title translation: "Excess Scaling and Transportation Problems".
Scaling Algorithms for Network Problems,
H. N. Gabow,
J. of Comp. and Sys. Sci., (31), 148-168, 1985.
Adaptive scaling
Beyond the Flow Decomposition Barrier,
A. V. Goldberg and S. Rao,
JACM (45), 753-782, 1998.