DIAMOND: a distributed algorithm for vertex coloring problems and resource allocation. Issue 6 (1st November 2019)

• Record Type: Journal Article
• Authors: Miri, Mohammadhasan; Mohamedpour, Kamal; Darmani, Yousef; Sarkar, Mahasweta
• Is Part Of: IET networks. Volume 8:Issue 6(2019)
• Page Start: 381
• Page End: 389
• Publication Date: 2019-11-01
• Subjects: graph colouring -- resource allocation -- distributed algorithms; modified LOCAL model -- DIAMOND -- GEOM graphs -- vertex colouring problem -- myriad applications -- computer networks -- maximum vertex degree -- distributed algorithm -- resource allocation algorithms -- distributed algorithms -- greedily generalised VCP; Computer network architectures -- Periodicals; Computer network protocols -- Periodicals; Information networks -- Periodicals; Telecommunication systems -- Periodicals; 004.605
• DOI: 10.1049/iet-net.2018.5204
• Languages: English
• ISSNs: 2047-4954

Abstract

Abstract : The vertex colouring problem (VCP) and its generalisations have myriad applications in computer networks. To solve the VCP with Δ + 1 colours, numerous distributed algorithms based on LOCAL model have been proposed to reduce time complexity (the number of rounds), where Δ is the maximum vertex degree in the graph. In this paper, the authors present a distributed algorithm based on modified LOCAL model (DIAMOND) that reduces the number of rounds to one. It greedily solves the VCP with at most Δ + 1 colours. Computational results on Geometry (GEOM) graphs show that the number of used colours to colour each instance using DIAMOND is about Δ + 1 / 2 . DIAMOND is easily extended to solve greedily generalised VCPs in only one round. Moreover, they present two efficient resource allocation algorithms using DIAMOND. They allocate more resource to the graph compared with ( Δ + 1 ) ‐colouring and even to ( d ¯ + 1 ) ‐colouring algorithms, where d ¯ is the average vertex degree of the graph. They run in two and Δ rounds.