Complexity analysis of a decentralised graph colouring algorithm
Duffy, K. R., O'Connell, N. and Sapozhnikov, A.. (2008) Complexity analysis of a decentralised graph colouring algorithm. Information Processing Letters, Vol.107 (No.2). pp. 60-63. ISSN 0020-0190Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.ipl.2008.01.002
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. (C) 2008 Elsevier B.V. All rights reserved.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Divisions:||Faculty of Science > Mathematics|
|Journal or Publication Title:||Information Processing Letters|
|Publisher:||Elsevier Science BV|
|Date:||16 July 2008|
|Number of Pages:||4|
|Page Range:||pp. 60-63|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)