Name
Abstract | ||
|---|---|---|
An (2,1)-labeling of a graph is an assignment from the vertex set () to the set of nonnegative integers such that |()−()|≥2 if and are adjacent and |()−()|≥1 if and are at distance 2, for all and in (). A -(2,1)-labeling is an (2,1)-labeling :()→{0,…,}, and the (2,1)-labeling problem asks the minimum , which we denote by (), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O( ) for more than a decade, and an O(min{ , })-time algorithm has appeared recently, where and are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for (2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for (,1)-labeling with a constant . |
Year | DOI | Venue |
|---|---|---|
2009 | https://doi.org/10.1007/s00453-012-9657-z | Algorithmica |
Keywords | DocType | Volume |
Frequency/channel assignment,Graph algorithm,L,(2,1)-Labeling,Vertex coloring | Conference | 66 |
Issue | ISSN | Citations |
3 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 0 | 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 |