LCS Publication Details
Publication Title: FINDING MINIMUM-COST CIRCULATIONS BY CANCELING NEGATIVE CYCLES
Publication Author: Goldberg, Andrew V.
Additional Authors: Tarjan, Robert E.
LCS Document Number: MIT-LCS-TM-334
Publication Date: 7-1-1987
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough around the cycle to saturate an are. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number on the iterations in this algorithm.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.