Efficient algorithms for maximum weight matchings in general graphs with small edge weights

zbMATH Open1423.05172MaRDI QIDQ5743485FDOQ5743485

Authors: Chien-Chung Huang, Telikepalli Kavitha 

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095226

Recommendations

• New algorithms for maximum weight matching and a decomposition theorem
• Scaling algorithms for weighted matching in general graphs
• Scaling algorithms for weighted matching in general graphs
• scientific article; zbMATH DE number 1304326
• Efficient algorithms for finding maximum matching in graphs

Mathematics Subject Classification ID

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

Cites Work

• Network flows. Theory, algorithms, and applications.
• Title not available (Why is that?)
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Paths, Trees, and Flowers
• On some techniques useful for solution of transportation network problems
• The Factorization of Linear Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matching theory
• Title not available (Why is that?)
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems
• Algorithms – ESA 2004
• Maximum matching and a polyhedron with 0,1-vertices
• Matrix multiplication via arithmetic progressions
• Maximum weight bipartite matching in matrix multiplication time
• A linear-time algorithm for a special case of disjoint set union
• Scaling Algorithms for the Shortest Paths Problem
• A scaling algorithm for maximum weight matching in bipartite graphs
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Title not available (Why is that?)
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Title not available (Why is that?)
• Clique partitions, graph compression and speeding-up algorithms
• Algorithms for dense graphs and networks on the random access computer
• Perfect matchings in \(O(n \log n)\) time in regular bipartite graphs
• Maximum matchings in planar graphs via Gaussian elimination
• A decomposition theorem for maximum weight bipartite matchings
• Global Price Updates Help
• A shortest augmenting path method for solving minimal perfect matching problems
• Maximum skew-symmetric flows
• Title not available (Why is that?)

Cited In (9)

• Efficient algorithms for finding maximum matching in graphs
• Fully dynamic maximal matching in \(O(\log n)\) update time (corrected version)
• A simple reduction from maximum weight matching to maximum cardinality matching
• Two dimensional maximum weight matching using Manhattan topology
• New algorithms for maximum weight matching and a decomposition theorem
• Fully dynamic maximal matching in \(O(\log n)\) update time
• Efficient algorithms for variants of weighted matching and assignment problems
• Solving maximum weighted matching on large graphs with deep reinforcement learning
• Output sensitive fault tolerant maximum matching

This page was built for publication: Efficient algorithms for maximum weight matchings in general graphs with small edge weights

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