A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs

DOI10.1145/3365006zbMath1454.68093OpenAlexW2986113791WikidataQ126798689 ScholiaQ126798689MaRDI QIDQ4973052

Sanjeev Khanna, Sharath Raghvendra, Mudabir Kabir Asathulla, Nathaniel Adam Lahn

Publication date: 2 December 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3365006

zbMATH Keywords

primal-dualscaling algorithmsminimum-cost matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

This page was built for publication: A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs