Complexity analysis of a decentralised graph colouring algorithm

作     者：Duffy, K. R. O'Connell, N. Sapozhnikov, A. 

作者机构：Natl Univ Ireland Hamilton Inst Maynooth Kildare Ireland Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Ctr Wiskunde & Informat NL-1098 SJ Amsterdam Netherlands 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2008年第107卷第2期

页      面：60-63页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Science Foundation Ireland, SFI, (03-IN3-I396, RFP-07-ENEF530) Science Foundation Ireland, SFI University College Cork, UCC, (SFI-04-RP1-I512) University College Cork, UCC 

主　　题：computational complexity graph algorithms randomised algorithms 

摘      要：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. (C) 2008 Elsevier B.V. All rights reserved.