On the distributed complexity of computing maximal matchings
From MaRDI portal
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
A maximal matching can be computed deterministically in \(O(\log^4n)\) rounds in the synchronous, message-passing model of distributed computation.
Cited in
(30)- Linear-in- lower bounds in the LOCAL model
- Distributed algorithm for approximating the maximum matching
- Improved deterministic distributed matching via rounding
- Improved distributed degree splitting and edge coloring
- Distributed maximum maintenance on hierarchically divided graphs
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- Distributed Algorithm for Better Approximation of the Maximum Matching
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- scientific article; zbMATH DE number 1303560 (Why is no real title available?)
- A time hierarchy theorem for the LOCAL model
- Network Decomposition and Distributed Derandomization (Invited Paper)
- Round compression for parallel matching algorithms
- Distributed graph algorithms and their complexity: an introduction
- Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
- Distributed half-integral matching and beyond
- Distributed half-integral matching and beyond
- (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
- Faster deterministic distributed MIS and approximate matching
- Distributed algorithms for covering, packing and maximum weighted matching
- Towards distributed two-stage stochastic optimization
- Local distributed rounding: generalized to MIS, matching, set cover, and beyond
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- Distributed edge coloring in time polylogarithmic in \({\Delta }\)
- On the distributed complexity of the semi-matching problem
- Distributed algorithms for random graphs
- A simple local 3-approximation algorithm for vertex cover
- Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs
This page was built for publication: On the distributed complexity of computing maximal matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784500)
