Approximating weighted matchings in parallel
From MaRDI portal
Publication:845697
DOI10.1016/J.IPL.2006.03.005zbMATH Open1184.68638OpenAlexW2039562302MaRDI QIDQ845697FDOQ845697
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
analysis of algorithmsapproximation algorithmsgraph algorithmsparallel algorithmsmaximum weight matching
Analysis of algorithms (68W40) Approximation algorithms (68W25) Parallel algorithms in computer science (68W10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Constructing a perfect matching is in random NC
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Matching is as easy as matrix inversion
- A Las Vegas RNC algorithm for maximum matching
- Approximating matchings in parallel
- Parallel approximation algorithms for maximum weighted matching in general graphs
- 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
Cited In (9)
- Parallel graph algorithms for finding weighted matchings and subgraphs in computational science
- Approximate Matching in Weighted Sequences
- Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs
- Best of two local models: centralized local and distributed local algorithms
- Approximating matchings in parallel
- Planar Maximum Matching: Towards a Parallel Algorithm
- (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
- Distributed algorithms for covering, packing and maximum weighted matching
- An efficient NC algorithm for approximate maximum weight matching
This page was built for publication: Approximating weighted matchings in parallel
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845697)
