TY - JOUR

T1 - A Linear Time Algorithm for L(2,1)-Labeling of Trees

AU - Hasunuma, Toru

AU - Ishii, Toshimasa

AU - Ono, Hirotaka

AU - Uno, Yushi

N1 - Funding Information:
A part of this article was presented in Proceedings of the Algorithms—ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009, Lecture Notes in Computer Science, vol. 5757, pp. 35–46, Springer, Berlin 2009 []. This work is partially supported by KAKENHI 20700002, 21680001, 23500022 and 24700001 and by the Kayamori Foundation of Informational Science Advancement.

PY - 2013/7

Y1 - 2013/7

N2 - An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|≥2 if x and y are adjacent and |f(x)-f(y)|≥1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)→{0,.,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ 4.5 n) for more than a decade, and an O(min{n 1.75,Δ 1.5 n})-time algorithm has appeared recently, where Δ and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.

AB - An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|≥2 if x and y are adjacent and |f(x)-f(y)|≥1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)→{0,.,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ 4.5 n) for more than a decade, and an O(min{n 1.75,Δ 1.5 n})-time algorithm has appeared recently, where Δ and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.

UR - http://www.scopus.com/inward/record.url?scp=84877826012&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877826012&partnerID=8YFLogxK

U2 - 10.1007/s00453-012-9657-z

DO - 10.1007/s00453-012-9657-z

M3 - Article

AN - SCOPUS:84877826012

SN - 0178-4617

VL - 66

SP - 654

EP - 681

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -