Distributed approximate matching

DOI10.1137/080714403MaRDI QIDQ3558010zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

distributed algorithmsgraph algorithmsmaximum matchingdynamic algorithmsdistributed approximation algorithms

Mathematics Subject Classification ID

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)

Recommendations

• Distributed approximate matching
• Improved Distributed Approximate Matching
• Distributed Weighted Matching
• Algorithms – ESA 2004
• Distributed approximate maximum matching in the CONGEST model

Cited in

(27)

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• 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
• New bounds for the controller problem
• Improved deterministic distributed matching via rounding
• Distributed maximum matching verification in CONGEST
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Improved Distributed Approximate Matching
• Distributed approximate maximum matching in the CONGEST model
• Improved deterministic distributed matching via rounding
• 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)