SIAM Journal on Computing · 1975 · 558 citations · 6 references
ComputingComputer ScienceAlgorithmsComputer NetworksEdge ComputingGraph AlgorithmsGraph TheoryNetwork ConnectivityNetwork Flow AlgorithmsNetwork FlowsNetwork OptimizationComputational Complexity Of Graph AlgorithmsDinic's AlgorithmGraph ConnectivityMaximum FlowMaximum Flow AlgorithmsMaximum Flow ProblemsNetwork Flow ProblemsVertex Connectivity
An algorithm of Dinic for finding the maximum flow in a network is described. It is then shown that if the vertex capacities are all equal to one, the algorithm requires at most $O(|V|^{1/2} \cdot |E|)$ time, and if the edge capacities are all equal to one, the algorithm requires at most $O(|V|^{2/3} \cdot |E|)$ time. Also, these bounds are tight for Dinic’s algorithm. These results are used to test the vertex connectivity of a graph in $O(|V|^{1/2} \cdot |E|^2 )$ time and the edge connectivity in $O(|V|^{5/3} \cdot |E|)$ time.
6
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations