Improved deterministic distributed matching via rounding

DOI10.4230/LIPICS.DISC.2017.17MaRDI QIDQ6487488zbMATH OpenFDO

Authors Manuela Fischer

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2017.17

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)

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

Cited in

(18)

• Sampling and output estimation in distributed algorithms and LCAs
• Best of two local models: centralized local and distributed local algorithms
• Distributed approximation for \(f\)-matching
• Approximating bipartite minimum vertex cover in the Congest model
• Towards distributed two-stage stochastic optimization
• 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
• Improved Distributed Approximate Matching
• Distributed approximate maximum matching in the CONGEST model
• Improved deterministic distributed matching via rounding
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• 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)