Thumbnail
Access Restriction
Subscribed

Author Goldberg, Andrew V. ♦ Rao, Satish
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Combinatorial optimization ♦ Maximum flows
Abstract We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual arc capacities. Our approach leads to an $\textit{O}(min(\textit{n}2/3,$ $\textit{m}1/2)\textit{m}$ $log(\textit{n}2/\textit{m})$ log $\textit{U})$ time bound for a network with $\textit{n}$ vertices, $\textit{m}$ arcs, and integral arc capacities in the range [1, …, $\textit{U}].$ This is a fundamental improvement over the previous time bounds. We also improve bounds for the Gomory-Hu tree problem, the parametric flow problem, and the approximate $\textit{s-t}$ cut problem.
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 1998-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 45
Issue Number 5
Page Count 15
Starting Page 783
Ending Page 797


Open content in new tab

   Open content in new tab
Source: ACM Digital Library