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, \cdots, \lambda\}$ to the vertices of the graph such that adjacent vertices are assigned integers of at least distance $h\geq 1$ apart and all vertices of distance three or less must be assigned different labels. %%(except for $h=0$, where adjacent nodes may have the same label). The aim of the $L(h,1,1)$-labeling problem is to minimize $\lambda$, denoted by $\lambda_{h,1,1}$ and called \emph{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)$, but the multiplicative factor depends on the maximum degree $\Delta$ and is too big to be of practical use. %where the multiplicative constant is exponential in their maximum degree $\Delta$. In this paper we give a linear time approximation algorithm for computing the more general $L\left(h,1,1\right)$-labeling for outerplanar graphs that is within additive constants of the optimum values.