| 作成者 |
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
| 関連DOI |
|
|
|
|
|
|
|
| 関連URI |
|
|
|
|
|
|
|
| 関連URI |
|
| 関連HDL |
|
| 関連情報 |
|
|
|
|
|
|
|
| 概要 |
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.続きを見る
|
Mendeley出力
n175-algorithm-L21tree