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
