Complexity analysis of a decentralised graph colouring algorithm

DOI10.1016/j.ipl.2008.01.002zbMath1186.68219OpenAlexW2129444820WikidataQ56269088 ScholiaQ56269088MaRDI QIDQ963399

Ken R. Duffy, Neil O'Connell, Artëm Sapozhnikov

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://eprints.maynoothuniversity.ie/1677/1/cfl.pdf

zbMATH Keywords

computational complexitygraph algorithmsrandomised algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• The solution of some random NP-hard problems in polynomial expected time
• Almost all k-colorable graphs are easy to color
• Locality in Distributed Graph Algorithms
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Worst-case time bounds for coloring and satisfiability problems
• On the complexity of distributed graph coloring

This page was built for publication: Complexity analysis of a decentralised graph colouring algorithm