Name
Abstract | ||
|---|---|---|
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 j f (x),f (y)j,2 if x and y are adjacent andj f (x),f (y)j,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) ! f0;:::; kg, 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 O( ,:75) time algorithm, which greatly improves the currently best known,result. Keywords. frequency/channel assignment, graph algorithm, L(2; 1)-labeling, vertex col- oring. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-69903-3_18 | SWAT |
Keywords | Field | DocType |
col | Discrete mathematics,Combinatorics,Johnson's algorithm,Computer science,Algorithm,Graph bandwidth,Kruskal's algorithm | Conference |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
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 |