The Library
Complexity analysis of a decentralised graph colouring algorithm
Tools
Tools
Tools
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-0190
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.ipl.2008.01.002
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. (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 |
| ISSN: | 0020-0190 |
| Date: | 16 July 2008 |
| Volume: | Vol.107 |
| Number: | No.2 |
| Number of Pages: | 4 |
| Page Range: | pp. 60-63 |
| Identification Number: | 10.1016/j.ipl.2008.01.002 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| URI: | http://wrap.warwick.ac.uk/id/eprint/29763 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
