Skip to main content

Minimum Cost Flows in Graphs with Unit Capacities

Author(s): Goldberg, Andrew V; Kaplan, Haim; Hed, Sagi; Tarjan, Robert E

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1xc1m
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGoldberg, Andrew V-
dc.contributor.authorKaplan, Haim-
dc.contributor.authorHed, Sagi-
dc.contributor.authorTarjan, Robert E-
dc.date.accessioned2021-10-08T19:47:34Z-
dc.date.available2021-10-08T19:47:34Z-
dc.date.issued2015en_US
dc.identifier.citationGoldberg, Andrew V., Haim Kaplan, Sagi Hed, and Robert E. Tarjan. "Minimum Cost Flows in Graphs with Unit Capacities." In 32nd International Symposium on Theoretical Aspects of Computer Science 30 (2015): pp. 406-419. doi:10.4230/LIPIcs.STACS.2015.406en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1xc1m-
dc.description.abstractWe consider the minimum cost flow problem on graphs with unit capacities and its special cases. In previous studies, special purpose algorithms exploiting the fact that capacities are one have been developed. In contrast, for maximum flow with unit capacities, the best bounds are proven for slight modifications of classical blocking flow and push-relabel algorithms. In this paper we show that the classical cost scaling algorithms of Goldberg and Tarjan (for general integer capacities) applied to a problem with unit capacities achieve or improve the best known bounds. For weighted bipartite matching we establish a bound of O( √ rm log C) on a slight variation of this algorithm. Here r is the size of the smaller side of the bipartite graph, m is the number of edges, and C is the largest absolute value of an arc-cost. This simplifies a result of [Duan et al. 2011] and improves the bound, answering an open question of [Tarjan and Ramshaw 2012]. For graphs with unit vertex capacities we establish a novel O( √ nm log(nC)) bound. We also give the first cycle canceling algorithm for minimum cost flow with unit capacities. The algorithm naturally generalizes the single source shortest path algorithm of [Goldberg 1995].en_US
dc.format.extent406 - 419en_US
dc.language.isoen_USen_US
dc.relation.ispartof32nd International Symposium on Theoretical Aspects of Computer Scienceen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleMinimum Cost Flows in Graphs with Unit Capacitiesen_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.STACS.2015.406-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
MinCostFlowsGraphsUnitCapacities.pdf691.63 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.