Distributed approximate matching
DOI10.1137/080714403zbMATH Open1200.68278OpenAlexW1993913882MaRDI QIDQ3558010FDOQ3558010
Authors: Zvi Lotker, Boaz Patt-Shamir, Adi Rosén 
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/080714403
Recommendations
distributed algorithmsgraph algorithmsmaximum matchingdynamic algorithmsdistributed approximation algorithms
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)
Cited In (27)
- Communication complexity of approximate matching in distributed graphs
- An efficient distributed algorithm for maximum matching in general graphs
- Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
- A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- On the distributed complexity of the semi-matching problem
- Distributed algorithm for approximating the maximum matching
- (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
- The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
- Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
- Distributed approximation of maximum independent set and maximum matching
- Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
- Constant-time local computation algorithms
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Efficient Distributed Weighted Matchings on Trees
- Distributed approximate matching
- Algorithms – ESA 2004
- Distributed Weighted Matching
- Improved deterministic distributed matching via rounding
- Distributed maximum matching verification in CONGEST
- New bounds for the controller problem
- Distributed approximate maximum matching in the CONGEST model
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- Improved Distributed Approximate Matching
- Improved deterministic distributed matching via rounding
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Local computation algorithms for graphs of non-constant degrees
This page was built for publication: Distributed approximate matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558010)
