Linear-in-delta lower bounds in the LOCAL model

DOI10.1145/2611462.2611467zbMath1321.68281arXiv1304.1007OpenAlexW2083116840MaRDI QIDQ2943612

Jukka Suomela, Mika Göös, Juho Hirvonen

Publication date: 3 September 2015

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

Full work available at URL: https://arxiv.org/abs/1304.1007

zbMATH Keywords

lower boundslocal distributed algorithmsmaximal edge packingmaximal fractional matching

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items (3)

Improved deterministic distributed matching via rounding ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Distributed Lower Bounds for Ruling Sets

This page was built for publication: Linear-in-delta lower bounds in the LOCAL model