Min-Cost Flow in Unit-Capacity Planar Graphs

DOI10.4230/LIPICS.ESA.2019.66MaRDI QIDQ5075811zbMATH OpenOpenAlexFDO

Authors Adam Karczmarz, Piotr Sankowski

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1907.02274

zbMATH Keywords

minimum-cost circulationminimum-cost flowplanar graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
• Max Flows in Planar Graphs with Vertex Capacities
• Minimum-cost flows in unit-capacity networks
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Algorithms for multicommodity flows in planar graphs

Cites work

• A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
• A faster algorithm for minimum-cost bipartite perfect matching in planar graphs
• A strongly polynomial minimum cost circulation algorithm
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An O(n n) algorithm for maximum st-flow in a directed planar graph
• Constructing maximal dynamic flows from static flows
• Decremental single-source reachability in planar digraphs
• Faster Scaling Algorithms for Network Problems
• Finding Minimum-Cost Circulations by Successive Approximation
• Flow in Planar Graphs with Multiple Sources and Sinks
• scientific article; zbMATH DE number 5485557 (Why is no real title available?)
• scientific article; zbMATH DE number 6850313 (Why is no real title available?)
• scientific article; zbMATH DE number 6297748 (Why is no real title available?)
• scientific article; zbMATH DE number 3235858 (Why is no real title available?)
• Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
• Improved bounds for shortest paths in dense distance graphs
• Minimum-cost flows in unit-capacity networks
• Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
• Multiple-source shortest paths in embedded graphs
• Multiple-source shortest paths in planar graphs
• NC algorithms for weighted planar perfect matching and related problems
• Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
• Network Flow and Testing Graph Connectivity
• New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
• On some techniques useful for solution of transportation network problems
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Recognition of probe proper interval graphs
• Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
• Structured recursive separator decompositions for planar graphs in linear time
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(5)

• Minimum-cost flows in unit-capacity networks
• Quasi-upward planar drawings with minimum curve complexity
• Holiest minimum-cost paths and flows in surface graphs
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
• Flow equivalent trees in undirected node-edge-capacitated planar graphs

Describes a project that uses

Uses Software

• RELAX4

This page was built for publication: Min-Cost Flow in Unit-Capacity Planar Graphs

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