Thumbnail
Access Restriction
Subscribed

Author Borradaile, Glencora ♦ Klein, Philip
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Maximum flow ♦ Planar graphs
Abstract We give the first correct $\textit{O}(\textit{n}$ log $\textit{n})$ algorithm for finding a maximum $\textit{st}-flow$ in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual $\textit{s}-to-\textit{t}$ path.
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 2009-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 56
Issue Number 2
Page Count 30
Starting Page 1
Ending Page 30


Open content in new tab

   Open content in new tab
Source: ACM Digital Library