| Creator |
|
|
|
|
|
|
|
| Language |
|
| Publisher |
|
| Date |
|
| Source Title |
|
| Vol |
|
| First Page |
|
| Last Page |
|
| Publication Type |
|
| Access Rights |
|
| Related DOI |
|
| Related DOI |
|
|
|
|
|
|
|
| Related URI |
|
|
|
|
|
|
|
| Related URI |
|
| Related HDL |
|
| Relation |
|
|
|
|
|
|
|
| Abstract |
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 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.show more
|
Export Mendeley
n175-algorithm-L21tree