MURAL - Maynooth University Research Archive Library



    Complexity analysis of a decentralised graph colouring algorithm


    Share and Export

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

    [thumbnail of cfl.pdf] PDF
    cfl.pdf
    Download (150kB)

    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: https://mu.eprints-hosting.org/id/eprint/1677
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads

    MURAL - Maynooth University Research Archive Library is powered by EPrints 3.4 which is developed by the School of Electronics and Computer Science at the University of Southampton. About EPrints | Accessibility