An O(n^{1.75}) Algorithm for L(2,1)-labeling of Trees
説明
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.
収録刊行物
-
- Lecture Notes in Computer Science
-
Lecture Notes in Computer Science 5124 185-197, 2008-07
Springer
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1050298532705732608
-
- NII論文ID
- 120006654464
-
- HANDLE
- 2324/14762
-
- 本文言語コード
- en
-
- 資料種別
- conference paper
-
- データソース種別
-
- IRDB
- CiNii Articles