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 ©1989
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and $\textit{canceling}$ it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in $&Ogr;(\textit{nm}(log$ $\textit{n})min{log(\textit{nC}),$ $\textit{m}$ log $\textit{n}})$ time on a network of $\textit{n}$ vertices, $\textit{m}$ arcs, and arc costs of maximum absolute value $\textit{C}.$ This bound is comparable to those of the fastest previously known algorithms.
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 1989-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 36
Issue Number 4
Page Count 14
Starting Page 873
Ending Page 886

Open content in new tab

   Open content in new tab
Source: ACM Digital Library