An O(n^{1.75}) Algorithm for L(2,1)-labeling of Trees

Algorithm Theory - SWAT 2008, 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008, ProceedingsAn 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 assignment 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. Tree is one of a few classes for which the problem is polynomially solvable, but still only an $mbox{O}(Delta^{4.5} n)$ time algorithm for a tree T has been known so far, where Δ is the maximum degree of T and n = |V(T)|. In this paper, we first show that an existent necessary condition for λ(T) = Δ + 1 is also sufficient for a tree T with $Delta=Omega(sqrt{n})$ , which leads a linear time algorithm for computing λ(T) under this condition. We then show that λ(T) can be computed in $mbox{O}(Delta^{1.5}n)$ time for any tree T. Combining these, we finally obtain an O(n^{1.75}) time algorithm, which substantially improves upon previously known results