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, . . . , lambda} to the nodes of the graph such that adjacent nodes are assigned integers of at least distance h a parts per thousand yen 1 apart and all nodes of distance three or less must be assigned different labels. The aim of the L(h, 1, 1)-labeling problem is to minimize lambda, 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)), but the multiplicative factor depends on the maximum degree Delta and is too big to be of practical use. 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.