On Lower Bounds for the Time and the Bit Complexity of Some Probabilistic Distributed Graph Algorithms

DOI10.1007/978-3-319-04298-5_21zbMath1432.68557OpenAlexW63554089MaRDI QIDQ2938103

John Michael Robson, Akka Zemmari, Allyx Fontaine, Yves Métivier

Publication date: 13 January 2015

Published in: SOFSEM 2014: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-04298-5_21

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (1)

Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings

This page was built for publication: On Lower Bounds for the Time and the Bit Complexity of Some Probabilistic Distributed Graph Algorithms