MURAL - Maynooth University Research Archive Library



    Complexity analysis of a decentralised graph colouring algorithm


    Duffy, Ken R. and O’Connell, N. and Sapozhnikov, A. (2008) Complexity analysis of a decentralised graph colouring algorithm. Information Processing Letters. ISSN 0020-0190

    [img] Download (150kB)


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which descisions are made locally with no information about the graph’s global structure is particuarly 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.

    Item Type: Article
    Keywords: Decentralised graph colouring algorithm; NP-hard; wireless computer networks; Computational complexity; Graph algorithms; Randomized algorithms; Hamilton Institute.
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Faculty of Science and Engineering > Mathematics and Statistics
    Item ID: 1677
    Depositing User: Hamilton Editor
    Date Deposited: 18 Nov 2009 10:02
    Journal or Publication Title: Information Processing Letters
    Publisher: Elsevier
    Refereed: Yes
    URI:
      Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year

      Origin of downloads

      Altmetric
      MURAL - Maynooth University Research Archive Library is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.