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

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

Cited in

(8)

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

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)