Complexity analysis of a decentralised graph colouring algorithm

K.R. Duffy; N. O'Connell; A. Sapozhnikov

doi:10.1016/j.ipl.2008.01.002

Complexity analysis of a decentralised graph colouring algorithm

K.R. Duffy, N. O'Connell, A. Sapozhnikov

Eurandom

Research output: Contribution to journal › Article › Academic › peer-review

27 Citations (Scopus)

Abstract

Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.

Original language	English
Pages (from-to)	60-63
Journal	Information Processing Letters
Volume	107
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2008.01.002
Publication status	Published - 2008

Access to Document

10.1016/j.ipl.2008.01.002

Cite this

@article{4de4ee9d11e1429fbd93eb665edf06ca,

title = "Complexity analysis of a decentralised graph colouring algorithm",

abstract = "Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.",

author = "K.R. Duffy and N. O'Connell and A. Sapozhnikov",

year = "2008",

doi = "10.1016/j.ipl.2008.01.002",

language = "English",

volume = "107",

pages = "60--63",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Complexity analysis of a decentralised graph colouring algorithm

AU - Duffy, K.R.

AU - O'Connell, N.

AU - Sapozhnikov, A.

PY - 2008

Y1 - 2008

N2 - Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.

AB - Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.

U2 - 10.1016/j.ipl.2008.01.002

DO - 10.1016/j.ipl.2008.01.002

M3 - Article

SN - 0020-0190

VL - 107

SP - 60

EP - 63

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Complexity analysis of a decentralised graph colouring algorithm

Abstract

Access to Document

Fingerprint

Cite this