A linear time algorithm for L(2,1)-labeling of trees

Details A linear time algorithm for L(2,1)-labeling of trees A linear time algorithm for L(2,1)-labeling of trees

2008-10-06

arxiv.org/abs/0810.0906v2

Computer Science

Data Structures and Algorithms

23 pages, 3 figures

Scientific paper

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)|\ge 2$ if $x$ and $y$ are adjacent and $|f(x)-f(y)|\ge 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)\to\{0,..., k\}$, and the L(2,1)-labeling problem asks the minimum $k$, which we denote by $\lambda(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 a very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been $\mO(\Delta^{4.5} n)$ for more than a decade, however, an $\mO(n^{1.75})$-time algorithm has been proposed recently, which substantially improved the previous one, where $\Delta$ is the maximum degree of $T$ and $n=|V(T)|$. In this paper, we finally establish a linear time algorithm for L(2,1)-labeling of trees.

Affiliated with

Also associated with

No associations

Rating

A linear time algorithm for L(2,1)-labeling of trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A linear time algorithm for L(2,1)-labeling of trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A linear time algorithm for L(2,1)-labeling of trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-205486