A linear-time approximation algorithm for weighted matchings in graphs
- 1 July 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 1 (1), 107-122
- https://doi.org/10.1145/1077464.1077472
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- A simpler linear time 2/3−ε approximation for maximum weight matchingInformation Processing Letters, 2004
- Accelerating screening of 3D protein data with a graph theoretical approachBioinformatics, 2003
- A simple approximation algorithm for the weighted matching problemInformation Processing Letters, 2002
- Quality matching and local improvement for multilevel graph-partitioningParallel Computing, 2000
- A theory of alternating paths and blossoms for proving correctness of the $$O(\sqrt V E)$$ general graph maximum matching algorithmCombinatorica, 1994
- Faster scaling algorithms for general graph matching problemsJournal of the ACM, 1991
- Efficient implementation of graph algorithms using contractionJournal of the ACM, 1989
- A survey of heuristics for the weighted matching problemNetworks, 1983
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on GraphsJournal of the ACM, 1976
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965