Complexity analysis of a decentralised graph colouring algorithm

DOI10.1016/J.IPL.2008.01.002zbMATH Open1186.68219DBLPjournals/ipl/DuffyOS08OpenAlexW2129444820WikidataQ56269088 ScholiaQ56269088MaRDI QIDQ963399FDOQ963399

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

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

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)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)