L(h,1,1)-Labeling of Outerplanar Graphs
An L(h,1,1)-labeling of a graph is an assignment of labels from the set of integers
{0, ... , l} to the vertices of the graph such that adjacent
vertices are assigned integers of at least distance h >= 1 apart
and all vertices of distance three or less must be assigned different labels.
The aim of the L(h,1,1)-labeling problem is to minimize l.
This minimum is denoted by lambda_{h,1,1} and called span of the L(h,1,1)-labeling.
As outerplanar graphs have bounded treewidth, the L(1,1,1)-labeling problem on outerplanar
graphs can be exactly solved in O(n^3), where the multiplicative constant is exponential in Delta.
In this paper we give a linear time approximation algorithm for computing the more general
L(h,1,1)-labeling for outerplanar graphs that is within additive constants of the optimum values.
Conference Version