Access Restriction

Author Goldberg, Andrew V. ♦ Tarjan, Robert E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1988
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract All previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the $\textit{preflow}$ concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense graphs, achieving an $\textit{O}(\textit{n}3)$ time bound on an $\textit{n}-vertex$ graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in $\textit{O}(\textit{nm}$ $log(\textit{n}2/\textit{m}))$ time on an $\textit{n}-vertex,$ $\textit{m}-edge$ graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running in $\textit{O}(\textit{n}2log$ $\textit{n})$ time using $\textit{n}$ processors and $\textit{O}(\textit{m})$ space is obtained. This time bound matches that of the Shiloach-Vishkin algorithm, which also uses $\textit{n}$ processors but requires $\textit{O}(\textit{n}2)$ space.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1988-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 35
Issue Number 4
Page Count 20
Starting Page 921
Ending Page 940

Open content in new tab

   Open content in new tab
Source: ACM Digital Library