Approximating weighted matchings in parallel

DOI10.1016/j.ipl.2006.03.005zbMath1184.68638OpenAlexW2039562302MaRDI QIDQ845697

Doratha E. Vinkemeier, Stefan Hougardy

Publication date: 29 January 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.03.005

zbMATH Keywords

analysis of algorithmsparallel algorithmsgraph algorithmsapproximation algorithmsmaximum weight matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Related Items (6)

(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ AN EFFICIENT NC ALGORITHM FOR APPROXIMATE MAXIMUM WEIGHT MATCHING

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel approximation algorithms for maximum weighted matching in general graphs
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• Constructing a perfect matching is in random NC
• Approximating matchings in parallel
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• A linear-time approximation algorithm for weighted matchings in graphs
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Approximating weighted matchings in parallel