Distributed Approximate Matching

DOI10.1137/080714403zbMath1200.68278OpenAlexW1993913882MaRDI QIDQ3558010

Adi Rosén, Zvi Lotker, Boaz Patt-Shamir

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

zbMATH Keywords

maximum matchinggraph algorithmsdistributed algorithmsdynamic algorithmsdistributed approximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (13)

Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ (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 ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ New bounds for the controller problem ⋮ Constant-time local computation algorithms ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2 ⋮ On the distributed complexity of the semi-matching problem ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

This page was built for publication: Distributed Approximate Matching