A distributed algorithm for vertex coloring problems in wireless networks

A lot of problems in computer networks are modeled by the vertex coloring problem (VCP), the multicoloring problem (MCP), the bandwidth coloring problem (BCP), and the bandwidth multicoloring problem (BMCP). To solve the VCP with Δ + 1 colors, a myriad distributed algorithms have been proposed to reduce time complexity (the number of rounds), where Δ is the maximum vertex degree in the graph. Time and communication complexities of these algorithms are functions of n and Δ , where n is the number of vertices in the graph. The MCP can be converted into VCP after transformation of the graph; the transformation increases the time and communication complexities. However, no distributed algorithms for BCP and BMCP have been proposed in the literature. In this paper, we propose a General Distributed Vertex Coloring Algorithm (GDVCA) to solve four problems in wireless networks. In GDVCA, some (and not necessarily all) vertices assign colors to themselves and their neighbors, which we refer to them as assigning vertices. The communication cost of GDVCA is very low; the number of messages transmitted by each assigning vertex is one and by the other vertices is zero. Assigning vertices assign the first available colors to uncolored vertices; moreover assigning vertices can use heuristic methods to choose the next proper vertex for coloring. Therefore, the number of colors used by the distributed algorithm GDVCA is significantly low. The number of time slots required to color a graph is O ( Δ 2 ) and at most n, where each round comprises several time slots.