On the Distributed Complexity of Computing Maximal Matchings

DOI10.1137/S0895480100373121zbMath0987.05079OpenAlexW2011595776MaRDI QIDQ2784500

Alessandro Panconesi, Michał Karoński, Michał Hanćkowiak

Publication date: 23 April 2002

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480100373121

zbMATH Keywords

graph algorithmdeterministicdistributed algorithmmaximal matchingsynchronous

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

Distributed algorithm for approximating the maximum matching ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well ⋮ Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings ⋮ Distributed algorithms for random graphs ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Improved deterministic distributed matching via rounding ⋮ Improved distributed degree splitting and edge coloring ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ 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 ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Round Compression for Parallel Matching Algorithms ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ 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