A computational comparison of the dinic and network simplex methods for maximum flow
Annals of Operations ResearchPublished 1 December 1988
Donald Goldfarb, Michael D. Grigoriadis
Citations90
SJR quartileQ1
SJR score1.09
SNIP1.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The implementation of two fundamentally different algorithms for solving the maximum flow problem: Dinic's method and the network simplex method are studied and a "steepest-edge" pivot selection criterion is developed that is easy to include in an existing networksimplex implementation.
Abstract
We study the implementation of two fundamentally different algorithms for solving the maximum flow problem: Dinic's method and the network simplex method. For the former, we present the design of a storage-efficient implementation. For the latter, we develop a "steepest-edge" pivot selection criterion that is easy to include in an existing network simplex implementation. We compare the computational efficiency of these two methods on a personal computer with a set of generated problems of up to 4 600 nodes and 27 000 arcs.
Keywords
Computer ScienceEngineering
American Mathematical MonthlyCombinatorial Optimization: Algorithms and Complexity.
6,028 Citations1984David Johnson, Christos H. Papadimitriou +1 more
Flows in networks
4,080 Citations1962D. R. Ford, D. R. Fulkerson
Journal of the ACMTheoretical Improvements in Algorithmic Efficiency for Network Flow Problems
2,522 Citations1972Jack Edmonds, Richard M. Karp
Upper bounds on the number of steps in these algorithms are derived, and are shown to improve on the upper bounds of earlier algorithms.
Canadian Journal of MathematicsMaximal Flow Through a Network
2,340 Citations1956L. R. Ford, D. R. Fulkerson
Society for Industrial and Applied Mathematics eBooksData Structures and Network Algorithms
2,067 Citations1983Robert E. Tarjan
This paper presents a meta-trees tree model that automates the very labor-intensive and therefore time-heavy and therefore expensive process of manually selecting trees to grow in a graph.
Birkhäuser Boston eBooksMaximal Flow Through a Network
1,856 Citations2009L. R. Ford, D. R. Fulkerson
Graph Algorithms
1,284 Citations1979Shimon Even
A thoroughly revised second edition of Shimon Even's Graph Algorithms, with a foreword by Richard M. Karp and notes by Andrew V Goldberg, explains algorithms in a formal but simple language with a direct and intuitive presentation.
Journal of Computer and System SciencesA data structure for dynamic trees
1,040 Citations1983Daniel D. Sleator, Robert E. Tarjan
Discrete MathematicsA characterization of the minimum cycle mean in a digraph
747 Citations1978Richard M. Karp
A simple characterization of λ∗, as well as an algorithm for computing it efficiently, is given, which is called the minimum cycle mean.
Journal of AlgorithmsAn O(logn) parallel connectivity algorithm
598 Citations1982Yossi Shiloach, Uzi Vishkin
It is conjectured that the barrier of O(log n) cannot be surpassed by any polynomial number of processors and that this performance cannot be achieved in the weaker model.
A new approach to the maximum flow problem
326 Citations1986Andrew V. Goldberg, Robert E. Tarjan
By incorporating the dynamic tree data structure of Sleator and Tarjan, a version of the algorithm running in O(nm log(n'/m)) time on an n-vertex, m-edge graph is obtained, as fast as any known method for any graph density and faster on graphs of moderate density.
Mathematical ProgrammingPivot selection methods of the Devex LP code
245 Citations1973Paula M. J. Harris
After a fresh look at the iteration process, the author introduces dynamic column weighting factors as a means of estimating gradients for the purpose of selecting a maximum gradient column.
Journal of AlgorithmsAn O(n2log n) parallel max-flow algorithm
226 Citations1982Yossi Shiloach, Uzi Vishkin
A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented, whose depth is O( n 3 ( log n) p) where p (p ≤ n) is the number of processors used.
Information Processing LettersAn O(|V|3) algorithm for finding maximum flows in networks
218 Citations1978Vishv Malhotra, Mohit Kumar +1 more
An O(V cubed) algorithm is given for finding maximum flow in capacitated networks and is being posted here to make it accessible to all in electronic form.
Mathematical ProgrammingA network simplex method
205 Citations1976William H. Cunningham
Simple combinatorial modifications are given which ensure finiteness in the primal simplex method for the transshipment problem and the upper-bounded primalsimplexmethod for the minimum cost flow problem.
Mathematical ProgrammingA practicable steepest-edge simplex algorithm
201 Citations1977Donald Goldfarb, John Reid
Results of computer comparisons on medium-scale problems indicate that the resulting algorithm requires less iterations but about the same overall time as the algorithm of Harris [8], which may be regarded as approximating the steepest-edge algorithm.
Operations ResearchNetworks and Basic Solutions
121 Citations1966Ellis L. Johnson
A labeling procedure which could be used to carry out the steps of the simplex algorithm for a network flow problem and a procedure to keep the solutions basic in the Ford-Fulkerson algorithm are given.
Mathematics of Operations ResearchTheoretical Properties of the Network Simplex Method
119 Citations1979William H. Cunningham
An example of cycling in the network simplex method is given and some restrictions on its occurrence are proved, and two methods which prevent cycling are shown to admit stalling.
Mathematical programming studiesAn efficient implementation of the network simplex method
89 Citations1986Michael D. Grigoriadis
This paper describes an efficient implementation of the network simplex method for solving large sparse minimum-cost network flow problems which employs an initial spanning tree of all artificial edges, a gradual penalty method for reducing infeasibilities and a sample pricing strategy which does not require adjacency-ordered edge lists.
Journal of Computer and System SciencesAn O(EVIog2V) algorithm for the maximal flow problem
63 Citations1980Zvi Galil, Amnon Naamad
An O(EV log2 V) algorithm for finding the maximal flow in networks is described, which is asymptotically better than the other known algorithms if E = O(V2−ϵ) for some ϵ > 0.1.
Operations Research LettersA simple version of Karzanov's blocking flow algorithm
61 Citations1984Robert E. Tarjan
This paper proposes a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.
Journal of the ACMPivot Strategies for Primal-Simplex Network Codes
58 Citations1978John M. Mulvey
It is again shown that the number of iterations, i e pivots, is a poor surrogate for the performance of primal-simplex network algorithms.
ACM Transactions on Mathematical SoftwareComputational Comparison of Eight Methods for the Maximum Network Flow Problem
45 Citations1980To-Yat Cheung
Computational comparison of eight methods for solving the maximum network flow problem shows that Dnuc's method is better than all of the other methods, and the performances of the depth-first and breadth-first methods are comparable to Dinic's method for small problems.
Acta InformaticaAn O(V 5/3 E 2/3) algorithm for the maximal flow problem
43 Citations1980Zvi Galil
A new algorithm for finding a maximal flow in a given network is presented that runs in time O(V5/3E2/3), where V and E are the number of the vertices and edges in the network.
Mathematical ProgrammingMore pathological examples for network flow problems
26 Citations1973Norman Zadeh
Two examples are presented, whereby O(n3) flow augmentations using tie-breaking variants of either the Edmonds—Karp shortest path or fewest reverse arcs in path maximum flow algorithms are required and it is not possible to substantially improve the performance of either algorithm by resolving ties.
Discrete Applied MathematicsAn extended abstract of an indepth algorithmic and computational study for maximum flow problems
18 Citations1980Fred Glover, Darwin Klingman +2 more
This study discloses several misconceptions about maximum flow algorithms whose challenge was overdue and investigates the first significant computational investigation of maximum flow methods.