Scaling Algorithms for Weighted Matching in General Graphs

DOI10.1145/3155301zbMath1451.05227arXiv1411.1919OpenAlexW2782000683MaRDI QIDQ4554953

Seth Pettie, Hsin-Hao Su, Ran Duan

Publication date: 12 November 2018

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

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

zbMATH Keywords

matching polytopescaling algorithmnon-bipartite graphs

Mathematics Subject Classification ID

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

Related Items (16)

Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers ⋮ A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints ⋮ A weight-scaling algorithm for \(f\)-factors of multigraphs ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ On matchings, T‐joins, and arc routing in road networks ⋮ Parameterized complexity of happy coloring problems ⋮ On the parallel complexity of constrained read-once refutations in UTVPI constraint systems ⋮ Recognizing when a preference system is close to admitting a master list ⋮ Weighted connected matchings ⋮ A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs ⋮ Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments ⋮ Unnamed Item ⋮ Unpopularity factor in the marriage and roommates problems ⋮ A \(2/3\)-approximation algorithm for vertex-weighted matching ⋮ Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths ⋮ Complexity and approximability of minimum path-collection exact covers

This page was built for publication: Scaling Algorithms for Weighted Matching in General Graphs