A faster distributed algorithm for computing maximal matchings deterministically

DOI10.1145/301308.301360MaRDI QIDQ2942765zbMATH OpenOpenAlexFDO

Authors Michal Karonski, Alessandro Panconesi, Michal Hanckowiak

Publication date 11 September 2015

Published in Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/301308.301360

Mathematics Subject Classification ID

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

Cited in

(7)

• Distributed backup placement in networks
• Distributed approximation for \(f\)-matching
• Round compression for parallel matching algorithms
• Distributed maximum matching verification in CONGEST
• Some simple distributed algorithms for sparse networks
• Distributed approximate maximum matching in the CONGEST model
• Improved deterministic distributed matching via rounding

This page was built for publication: A faster distributed algorithm for computing maximal matchings deterministically

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942765)