Complexity analysis of a decentralised graph colouring algorithm

https://doi.org/10.1016/j.ipl.2008.01.002Get rights and content

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.

References (10)

There are more references available in the full text version of this article.

Cited by (29)

  • Eventually lattice-linear algorithms

    2024, Journal of Parallel and Distributed Computing
  • A learning approach to decentralised beacon scheduling

    2016, Ad Hoc Networks
    Citation Excerpt :

    Note that, even in the case of collisions of beacons when certain information cannot be assessed, nodes may be able to obtain the slot selection in their neighbourhood via other neighbours. Therefore, convergence proofs as the one presented in [26] or the extension described in [27], in which an approach based on a flame-front of dissatisfied nodes is considered, are not directly applicable in this case. We have first evaluated the algorithm presented in this work in random unit disk graphs with given characteristics in order to obtain conclusions under controlled settings.

  • WLAN channel selection without communication

    2012, Computer Networks
    Citation Excerpt :

    Then the CFL algorithm converges, with probability one, to a non-interfering channel allocation. We omit our proof of this result [10] and a more detailed analysis [11]. The proof actually provides a partial answer to a further question, namely how quickly the algorithm converges to a non-interfering allocation.

  • Inducing Lattices in Non-Lattice-Linear Problems

    2023, Proceedings of the IEEE Symposium on Reliable Distributed Systems
View all citing articles on Scopus
View full text