An O(EVIog2V) algorithm for the maximal flow problem

Journal of Computer and System SciencesPublished 1 October 1980

Zvi Galil, Amnon Naamad

DOI10.1016/0022-0000(80)90035-5

Source URL

Citations63

SJR quartileQ1

SJR score1.03

SNIP1.08

TL;DR

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.

Abstract

An O(EV log2 V) algorithm for finding the maximal flow in networks is described. It is asymptotically better than the other known algorithms if E = O(V2−ϵ) for some ϵ > 0. The analysis of the running time exploits the discovery of a phenomenon similar to (but more general than) path compression, although the "union find" algorithm is not used. The time bound is shown to be tight in terms of V and E by exhibiting a family of networks that require Ω(EV log2V) time.1

Keywords

Computer ScienceEngineering

The Design and Analysis of Computer Algorithms

9,456 Citations1974Alfred V. Aho, John E. Hopcroft

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.

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

View PDF

Birkhäuser Boston eBooksMaximal Flow Through a Network

1,856 Citations2009L. R. Ford, D. R. Fulkerson

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.

View PDF

SIAM Journal on ComputingMaximum Flow in Planar Networks

120 Citations1979Alon Itai, Yossi Shiloach

Efficient algorithms for finding maximum flow in planar networks are presented and take advantage of the planarity and are superior to the most efficient algorithms to date.

A new algorithm for the maximal flow problem

28 Citations1978Zvi Galil

A new algorithm for finding the maximal flow in a given network is presented and it is shown that it runs in time O(V5/3E2/3) or O(n2.33) where n = V + E is the length of the input.

Biased 2-3 trees

21 Citations1980Samuel W. Bent, Daniel D. Sleator +1 more

A new data structure for maintaining collections of weighted items that is simpler than previous proposals, but the running time must be amortized over a sequence of operations to achieve the time bounds.

Theoretical Computer ScienceOn the theoretical efficiency of various network flow algorithms

12 Citations1981Zvi Galil

The time bounds of various algorithms for finding the maximal flow in networks are shown to be tight by constructing one parametrized family of network flow problems and showing that the algorithms achieve the corresponding bounds on inputs from this family.