A Self-Stabilizing Algorithm for L(2,1)-Labeling Trees

P. Chaudhuri and H. Thompson (Barbados)


Algorithms, Distributed system, Self-stabilization, Graph coloring


The L(2, 1)-labeling problem for a graph G is a variation of the standard graph coloring problem. Here, we seek to assign a label (color) 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 { + 2}-L(2, 1)-label a rooted tree T in O(n) rounds.

Important Links:

Go Back