Back to Search
Start Over
Complexity analysis of a decentralised graph colouring algorithm
- Source :
- Information Processing Letters, 107(2), 60-63. Elsevier, Information Processing Letters, 107(2), 60-63
- Publication Year :
- 2008
-
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.
- Subjects :
- Computational complexity theory
business.industry
Graph colouring
Mathematical statistics
Data_MISCELLANEOUS
Information processing
Astrophysics::Cosmology and Extragalactic Astrophysics
Mathematics & Statistics
Computer Science Applications
Theoretical Computer Science
Randomized algorithm
Signal Processing
Graph (abstract data type)
Wireless
Chromatic scale
business
Algorithm
Astrophysics::Galaxy Astrophysics
Information Systems
Mathematics
Hamilton Institute
Subjects
Details
- Language :
- English
- ISSN :
- 00200190 and 18726119
- Database :
- OpenAIRE
- Journal :
- Information Processing Letters, 107(2), 60-63. Elsevier, Information Processing Letters, 107(2), 60-63
- Accession number :
- edsair.doi.dedup.....6a57a8470fcf6cf8311d6d1a442ef61c