Distributed approximate matching

DOI10.1145/1281100.1281126MaRDI QIDQ5401409zbMATH OpenOpenAlexFDO

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

Publication date 13 March 2014

Published in Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1281100.1281126

zbMATH Keywords

distributed algorithmsgraph algorithmsmaximum matchingdynamic algorithmsdistributed approximation algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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

(18)

• Communication complexity of approximate matching in distributed graphs
• Communication complexity of approximate maximum matching in the message-passing model
• Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
• Theoretical underpinnings for maximal clique enumeration on perturbed graphs
• Dynamic approximate vertex cover and maximum matching
• Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
• Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
• Distributed algorithm for approximating the maximum matching
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Distributed graph algorithms and their complexity: an introduction
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Efficient Distributed Weighted Matchings on Trees
• Algorithms – ESA 2004
• Distributed Weighted Matching
• Distributed algorithms for covering, packing and maximum weighted matching
• Improved Distributed Approximate Matching
• Improved deterministic distributed matching via rounding
• 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 Q5401409)