Improved deterministic distributed matching via rounding
DOI10.4230/LIPICS.DISC.2017.17zbMATH Open1515.68366MaRDI QIDQ6487488FDOQ6487488
Authors: Manuela Fischer 
Publication date: 3 February 2023
Recommendations
maximal matchingdistributed graph algorithmsdeterministic distributed algorithmsmaximum matching approximationrounding linear programs
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 (15)
- Distributed approximation for \(f\)-matching
- Best of two local models: centralized local and distributed local algorithms
- Distributed approximation of maximum independent set and maximum matching
- Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
- Distributed computing in the asynchronous LOCAL model
- Round compression for parallel matching algorithms
- Round compression for parallel matching algorithms
- A time hierarchy theorem for the LOCAL model
- Distributed maximum matching verification in CONGEST
- The Match-Maker: Constant-Space Distributed Majority via Random Walks
- Distributed approximate maximum matching in the CONGEST model
- Improved Distributed Approximate Matching
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- 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)
