Minimum-cost flows in unit-capacity networks

DOI10.1007/s00224-017-9776-7zbMath1379.05049OpenAlexW2614327298MaRDI QIDQ1693987

Haim Kaplan, Sagi Hed, Andrew V. Goldberg, Robert Endre Tarjan

Publication date: 1 February 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9776-7

zbMATH Keywords

algorithmsassignment problembipartite matchingminimum-cost flows

Mathematics Subject Classification ID

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

Related Items (4)

Largest Weight Common Subtree Embeddings with Distance Penalties ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Min-Cost Flow in Unit-Capacity Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• Scaling algorithms for network problems
• Finding minimum-cost flows by double scaling
• On the computational behavior of a polynomial-time network flow algorithm
• Finding Minimum-Cost Circulations by Successive Approximation
• Network Flow and Testing Graph Connectivity
• Buckets, Heaps, Lists, and Monotone Priority Queues
• Global Price Updates Help
• Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m^10/7 log W) Time (Extended Abstract)
• Faster Scaling Algorithms for Network Problems
• Scaling Algorithms for the Shortest Paths Problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Minimum-cost flows in unit-capacity networks