Minimum cost flows in graphs with unit capacities

DOI10.4230/LIPICS.STACS.2015.406MaRDI QIDQ2955012zbMATH OpenFDO

Authors Andrew V. Goldberg, Haim Kaplan, Sagi Hed, Robert E. Tarjan

Publication date 24 January 2017

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2015.406

zbMATH Keywords

bipartite matchingcost scalingminimum cost flowunit capacity

Mathematics Subject Classification ID

Flows in graphs (05C21) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Minimum-cost flows in unit-capacity networks
• Finding minimum-cost flows by double scaling
• Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
• The cost scaling algorithm for bipartite networks
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm

Cited in

(8)

• Minimum-cost flows in unit-capacity networks
• Parameterized algorithms and kernels for almost induced matching
• The cost scaling algorithm for bipartite networks
• Almost induced matching: linear kernels and parameterized algorithms
• Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
• Holiest minimum-cost paths and flows in surface graphs
• A \(5k\)-vertex kernel for 3-path vertex cover
• A census of graph-drawing algorithms based on generalized transversal structures

This page was built for publication: Minimum cost flows in graphs with unit capacities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955012)