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)

• An efficient distributed algorithm for maximum matching in general graphs
• Improved deterministic distributed matching via rounding
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
• Algorithms – ESA 2004
• Distributed Weighted 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
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Efficient Distributed Weighted Matchings on Trees
• On the distributed complexity of the semi-matching problem
• 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
• New bounds for the controller problem
• Improved deterministic distributed matching via rounding
• Distributed algorithm for approximating the maximum matching
• Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
• Communication complexity of approximate matching in distributed graphs
• Constant-time local computation algorithms
• Local computation algorithms for graphs of non-constant degrees
• Distributed approximate maximum matching in the CONGEST model
• Distributed maximum matching verification in CONGEST
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Distributed approximation of maximum independent set and maximum matching
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Distributed approximate matching
• Improved Distributed Approximate Matching

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)