Scaling algorithms for weighted matching in general graphs

DOI10.1145/3155301MaRDI QIDQ4554953zbMATH OpenOpenAlexFDO

Authors Ran Duan, Seth Pettie, Hsin-Hao Su

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

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

Abstract: We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in $O(msqrtnlog(nN))$ time, $O(msqrtn)$ per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs. Here $m,n,$ and $N$ bound the number of edges, vertices, and magnitude of any edge weight. Our result improves on a 25-year old algorithm of Gabow and Tarjan, which runs in $O(msqrtnlognalpha(m,n)log(nN))$ time.

Recommendations

• Scaling algorithms for weighted matching in general graphs
• A scaling algorithm for maximum weight matching in bipartite graphs
• Faster scaling algorithms for general graph matching problems
• Implementation of O ( nm log n ) weighted matchings in general graphs
• Fast and Simple Algorithms for Weighted Perfect Matching

Cited in

(33)

• Weighted connected matchings
• Data Reduction for Maximum Matching on Real-World Graphs
• Approximate min-sum subset convolution
• Implementation of O ( nm log n ) weighted matchings in general graphs
• Complexity and approximability of minimum path-collection exact covers
• scientific article; zbMATH DE number 7559206 (Why is no real title available?)
• A distributed-memory algorithm for computing a heavy-weight perfect matching on bipartite graphs
• A weight-scaling algorithm for \(f\)-factors of multigraphs
• Traversing combinatorial 0/1-polytopes via optimization
• Maximum cardinality \(f\)-matching in time \(O(n^{2/3}m)\)
• Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• Algorithms for weighted matching generalizations. II: f-factors and the special case of shortest paths
• Weighted connected matchings
• On matchings, T‐joins, and arc routing in road networks
• scientific article; zbMATH DE number 3902700 (Why is no real title available?)
• Constrained read-once refutations in UTVPI constraint systems: a parallel perspective
• A scaling algorithm for maximum weight matching in bipartite graphs
• Unpopularity factor in the marriage and roommates problems
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
• A scaling algorithm for weighted f-factors in general graphs
• Adapting stable matchings to forced and forbidden pairs
• A \(2/3\)-approximation algorithm for vertex-weighted matching
• Popularity on the roommate diversity problem
• Algorithms for symmetric Birkhoff-von Neumann decomposition of symmetric doubly stochastic matrices
• An O(EV\log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs
• Efficient algorithms for maximum weight matchings in general graphs with small edge weights
• Parameterized complexity of happy coloring problems
• Scaling algorithms for weighted matching in general graphs
• Faster scaling algorithms for general graph matching 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
• Maximum flow and minimum-cost flow in almost-linear time

This page was built for publication: Scaling algorithms for weighted matching in general graphs

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