Name
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 L(2,1)-labeling f:V(G)-{0,...,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by @l(G), among all possible L(2,1)-labelings. 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 O(@D^4^.^5n) time algorithm for a tree T has been known so far, where @D is the maximum degree of T and n=|V(T)|. In this paper, we first show that an existent necessary condition for @l(T)=@D+1 is also sufficient for a tree T with @D=@W(n), which leads to a linear time algorithm for computing @l(T) under this condition. We then show that @l(T) can be computed in O(@D^1^.^5n) time for any tree T. Combining these, we finally obtain an O(n^1^.^7^5) time algorithm, which substantially improves upon previously known results. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.04.025 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
maximum degree,existent necessary condition,polynomially solvable,Graph algorithm,possible L,l2,graph algorithm,Vertex coloring,1 ) -labeling,tree T.,linear time algorithm,vertex coloring.,minimum k,frequency/channel assignment,graph G,time algorithm,nonnegative integer,L ( 2,1-labeling,Frequency/channel assignment | Journal | 410 |
Issue | ISSN | Citations |
38-40 | Theoretical Computer Science | 6 |
PageRank | References | Authors |
0.45 | 9 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toru Hasunuma | 1 | 142 | 16.00 |
| Toshimasa Ishii | 2 | 110 | 17.03 |
| Hirotaka Ono | 3 | 400 | 56.98 |
| yushi uno | 4 | 222 | 28.80 |