Improved deterministic distributed matching via rounding

DOI10.4230/LIPICS.DISC.2017.17zbMATH Open1515.68366MaRDI QIDQ6487488FDOQ6487488

Manuela Fischer

Publication date: 3 February 2023

Recommendations

• Improved deterministic distributed matching via rounding
• Distributed approximate maximum matching in the CONGEST model
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Improved Distributed Approximate Matching
• Distributed approximate matching

zbMATH Keywords

maximal matchingdistributed graph algorithmsdeterministic distributed algorithmsmaximum matching approximationrounding linear programs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

Cited In (10)

• A Time Hierarchy Theorem for the LOCAL Model
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• Distributed approximation for \(f\)-matching
• Distributed Approximate Maximum Matching in the CONGEST Model.
• Distributed computing in the asynchronous LOCAL model
• Distributed maximum matching verification in CONGEST
• The Match-Maker: Constant-Space Distributed Majority via Random Walks
• Improved Distributed Approximate Matching
• Improved deterministic distributed matching via rounding
• Network Decomposition and Distributed Derandomization (Invited Paper)

This page was built for publication: Improved deterministic distributed matching via rounding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487488)