Name
Abstract | ||
|---|---|---|
The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,…,k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O *((k+1)n ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006n ). Furthermore we show that dynamic programming can be used to establish an O(3.8730n ) algorithm to compute an optimal L(2,1)-labeling. |
Year | DOI | Venue |
|---|---|---|
2011 | https://doi.org/10.1007/s00453-009-9302-7 | Algorithmica |
Keywords | Field | DocType |
Graph,Algorithm,Moderately exponential time algorithm,L,(2,1)-labeling | Frequency assignment problem,Integer,Dynamic programming,Discrete mathematics,Graph,NP-complete,Combinatorics,Exponential function,Vertex (geometry),Vertex (graph theory),Algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
59 | 2 | 0178-4617 |
Citations | PageRank | References |
20 | 1.02 | 18 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frédéric Havet | 1 | 433 | 55.15 |
| Martin Klazar | 2 | 282 | 31.64 |
| Jan Kratochvíl | 3 | 1751 | 151.84 |
| Dieter Kratsch | 4 | 1957 | 146.89 |
| Mathieu Liedloff | 5 | 243 | 24.23 |