Parallel approximation algorithms for maximum weighted matching in general graphs

DOI10.1016/S0020-0190(00)00128-9zbMath1339.05406OpenAlexW2023492687MaRDI QIDQ294847

Zhi-Zhong Chen, Ryuhei Uehara

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000001289?np=y

zbMATH Keywords

parallel algorithmsgraph algorithmsapproximation algorithmsmaximum weighted matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Approximating weighted matchings in parallel ⋮ Structural results on matching estimation with applications to streaming ⋮ On graph problems in a semi-streaming model ⋮ AN EFFICIENT NC ALGORITHM FOR APPROXIMATE MAXIMUM WEIGHT MATCHING

Cites Work

• An improved parallel algorithm for maximal matching
• Approximation algorithms for weighted matching
• Constructing a perfect matching is in random NC
• The complexity of circuit value and network stability
• Approximating matchings in parallel
• A survey of heuristics for the weighted matching problem
• Efficient algorithms for finding maximum matching in graphs
• Paths, Trees, and Flowers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item