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)
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)
