A simple reduction from maximum weight matching to maximum cardinality matching
type: Item
instance of: scholarly article
title: A simple reduction from maximum weight matching to maximum cardinality matching
zbMATH Open document ID: 1248.05161
author: Seth Pettie
published in: Information Processing Letters
publication date: 2012-10-23T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6098108
zbMATH Keywords: graph algorithms
zbMATH Keywords: maximum matching
zbMATH Keywords: maximum weight matching
zbMATH Keywords: maximum cardinality matching
MaRDI profile type: Publication
full work available at URL: j.ipl.2012.08.010
OpenAlex ID: W2098645185
cites work: A decomposition theorem for maximum weight bipartite matchings
cites work: Q5743485
cites work: Scaling algorithms for network problems
cites work: Q5743486
cites work: Maximum skew-symmetric flows and matchings
cites work: Global Price Updates Help
cites work: Clique partitions, graph compression and speeding-up algorithms
cites work: Algebraic Algorithms for Matching and Matroid Problems
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Q5624995
cites work: A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
cites work: Faster scaling algorithms for general graph matching problems
cites work: Algorithms for dense graphs and networks on the random access computer
cites work: Deterministic sorting in O ( n log log n ) time and linear space
cites work: Integer priority queues with decrease key in constant time and the single source shortest paths problem
cites work: Equivalence between priority queues and sorting
cites work: Maximum weight bipartite matching in matrix multiplication time
cites work: Faster Scaling Algorithms for Network Problems
cites work: New scaling algorithms for the assignment and minimum mean cycle problems
cites work: Q3138921
cites work: Maximum matchings in planar graphs via Gaussian elimination
cites work: Q2934588
cites work: Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Paths, Trees, and Flowers
cites work: An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
DOI: 10.1016/J.IPL.2012.08.010
description: scientific article; zbMATH DE number 6098108