On the time and the bit complexity of distributed randomised anonymous ring colouring

DOI10.1016/J.TCS.2012.03.028zbMath1296.68191OpenAlexW2079726477MaRDI QIDQ391396

Nasser Saheb-Djahromi, John Michael Robson, Yves Métivier, Akka Zemmari

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.028

zbMATH Keywords

Mellin transformcolouringprobabilistic analysistime complexitybit complexityrandomised distributed graph algorithmring graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Cites Work

• About randomised distributed graph colouring and graph partition algorithms
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Simple distributed \(\Delta+1\)-coloring of graphs
• Bit complexity of breaking and achieving symmetry in chains and rings
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• On the complexity of distributed graph coloring
• Unnamed Item
• Unnamed Item

This page was built for publication: On the time and the bit complexity of distributed randomised anonymous ring colouring