| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429182 | Information Processing Letters | 2008 | 4 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
