Complexity analysis of a decentralised graph colouring algorithm

DOI10.1016/J.IPL.2008.01.002MaRDI QIDQ963399zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ken R. Duffy, Neil O'Connell, Artem 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

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

Recommendations

• Simple decentralized graph coloring
• scientific article; zbMATH DE number 2083800
• Graph colouring algorithms
• On the complexity of distributed graph coloring
• On the complexity of distributed graph coloring with local minimality constraints

Cites work

• scientific article; zbMATH DE number 3608053 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Almost all k-colorable graphs are easy to color
• Locality in Distributed Graph Algorithms
• On the complexity of distributed graph coloring
• The solution of some random NP-hard problems in polynomial expected time
• Worst-case time bounds for coloring and satisfiability problems

Cited in

(2)

• scientific article; zbMATH DE number 2083800 (Why is no real title available?)
• Simple decentralized graph coloring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963399)