A Self-Stabilizing Algorithm for Radio-Coloring Directed Trees

P. Chaudhuri and H. Thompson (Barbados)


Algorithms, Distributed system, Self-stabilization, Graph coloring


The radio channel assignment problem may be modeled as a graph labeling problem where each node of the graph G represents a radio transmitter and integer labels denote radio channels. Each pair of interfering transmitters from an edge in G and we seek a labeling of G such that some predefined set of constraints are met. One of the more well known variations is the L(2, 1)-labeling problem. Here, we seek to assign a label to each node of G such that nodes a distance of two apart are assigned unique labels and adjacent nodes receive labels which are at least two apart. In this paper, we present a self-stabilizing algorithm which will 4-L(2, 1)-label a rooted directed tree T r in O(n2 ) moves or O(n) rounds.

Important Links:

Go Back