### Beyond the flow decomposition barrierBeyond the flow decomposition barrier

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

Source: ACM Digital Library