A simple reduction from maximum weight matching to maximum cardinality matching
From MaRDI portal
Publication:456169
DOI10.1016/j.ipl.2012.08.010zbMath1248.05161OpenAlexW2098645185MaRDI QIDQ456169
Publication date: 23 October 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2012.08.010
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
Linear-Time Approximation for Maximum Weight Matching ⋮ Unnamed Item ⋮ Exact and approximation algorithms for weighted matroid intersection
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum weight bipartite matching in matrix multiplication time
- Scaling algorithms for network problems
- New scaling algorithms for the assignment and minimum mean cycle problems
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Maximum skew-symmetric flows and matchings
- Clique partitions, graph compression and speeding-up algorithms
- Algorithms for dense graphs and networks on the random access computer
- Maximum matchings in planar graphs via Gaussian elimination
- A Decomposition Theorem for Maximum Weight Bipartite Matchings
- Equivalence between priority queues and sorting
- Algebraic Algorithms for Matching and Matroid Problems
- Deterministic sorting in O ( n log log n ) time and linear space
- An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
- Faster scaling algorithms for general graph matching problems
- Global Price Updates Help
- Faster Scaling Algorithms for Network Problems
- Paths, Trees, and Flowers
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- Maximum matching and a polyhedron with 0,1-vertices
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
This page was built for publication: A simple reduction from maximum weight matching to maximum cardinality matching
