Complexity analysis of a decentralised graph colouring algorithm
type: Item
instance of: scholarly article
title: Complexity analysis of a decentralised graph colouring algorithm
zbMATH Open document ID: 1186.68219
author: Ken R. Duffy
author: Neil O'Connell
author: Artem Sapozhnikov
published in: Information Processing Letters
publication date: 2010-04-19T00:00:00Z
full work available at URL: cfl.pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5694954
zbMATH Keywords: computational complexity
zbMATH Keywords: graph algorithms
zbMATH Keywords: randomised algorithms
MaRDI profile type: Publication
OpenAlex ID: W2129444820
Wikidata QID: Q56269088
cites work: A Spectral Technique for Coloring Random 3-Colorable Graphs
cites work: The solution of some random NP-hard problems in polynomial expected time
cites work: Worst-case time bounds for coloring and satisfiability problems
cites work: Q4198056
cites work: Q4173377
cites work: On the complexity of distributed graph coloring
cites work: Locality in Distributed Graph Algorithms
cites work: Almost all k-colorable graphs are easy to color
DOI: 10.1016/J.IPL.2008.01.002
DBLP publication ID: journals/ipl/DuffyOS08
description: scientific article; zbMATH DE number 5694954