Name
Abstract | ||
|---|---|---|
An L(2, 1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L(2, 1)-span of a graph is the minimum possible span of its L(2, 1)- labelings. We show how to compute the L(2, 1)-span of a connected graph in time O*(2.6488n). Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3.2361, with 3 seemingly having been the Holy Grail. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-20877-5_9 | Theoretical Computer Science |
Keywords | Field | DocType |
adjacent vertex,exact exponential time algorithm,time o,connected graph,holy grail,nonnegative integer,exact algorithm,minimum possible span,exponential function,maximum label | Discrete mathematics,Combinatorics,Graph power,Vertex (graph theory),Graph labeling,Cycle graph,Neighbourhood (graph theory),Mathematics,Complement graph,Path graph,Edge-graceful labeling | Conference |
Volume | ISSN | Citations |
6648 | 0302-9743 | 7 |
PageRank | References | Authors |
0.52 | 22 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Konstanty Junosza-Szaniawski | 1 | 39 | 12.24 |
| Jan Kratochvíl | 2 | 1751 | 151.84 |
| Mathieu Liedloff | 3 | 243 | 24.23 |
| Peter Rossmanith | 4 | 1000 | 61.03 |
| Pawel Rzazewski | 5 | 42 | 19.73 |