A Linear Time Algorithm for L(2,1)-Labeling of Trees
A Linear Time Algorithm for L(2,1)-Labeling of Trees
复制标题
DOI：
10.1007/s00453-012-9657-z
复制
发表时间：
2008-10
期刊：
影响因子：
1.1
通讯作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
中科院分区：
文献类型：
--
作者：
Toru Hasunuma;Toshimasa Ishii;H. Ono;Yushi Uno
图G的L（2，1）-标号是从顶点集V（G）到非负整数集的一个赋值，使得|f（x）-f（y）|≥2，如果x相邻且|f（x）-f（y）|≥1，如果x和y在距离2处，对所有x和y V（G）。Ak-L（2，1）-标号是L（2，1）-标号f：V（G）→{0，.，k}，L（2，1）-标号问题要求k在所有可能的赋值中取最小值，记为λ（G）。众所周知，这个问题是NP-困难的，即使是树宽为2的图，树是少数几个类的问题是多项式可解的。最近又出现了一个O（min{n1. 75，Δ 1. 5 n}）时间的算法，其中Δ和n分别是输入树的最大度和顶点数，但如果在线性时间内可解，则该算法是开放的。本文通过建立树的L（2，1）-标号的线性时间算法解决了这个问题。此外，我们证明了它可以推广到一个线性时间算法的L（p，1）-标号与常数。
AnL(2,1)-labeling of a graphGis an assignmentffrom the vertex setV(G) to the set of nonnegative integers such that |f(x)−f(y)|≥2 ifxandyare adjacent and |f(x)−f(y)|≥1 ifxandyare at distance 2, for allxandyinV(G). Ak-L(2,1)-labeling is anL(2,1)-labelingf:V(G)→{0,…,k}, and theL(2,1)-labeling problem asks the minimumk, 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.5n) for more than a decade, and an O(min{n1.75,Δ1.5n})-time algorithm has appeared recently, whereΔandnare 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 forL(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm forL(p,1)-labeling with a constantp.