HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Exact algorithms for $L(2,1)$-labeling of graphs

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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, \dots ,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\ge 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$ -- here the running time of our algorithm is $O(1.3006^n)$. % $O(1.3161^n)$. Furthermore we show that dynamic programming can be used to establish %an $O(c^n)$ algorithm to compute an optimal $L(2,1)$-labeling, for a constant $c< 4$. an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling.
Document type :
Reports

Cited literature [17 references]

https://hal.inria.fr/inria-00303330
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Monday, July 21, 2008 - 10:45:03 PM
Last modification on : Sunday, May 1, 2022 - 3:15:07 AM
Long-term archiving on: : Monday, May 31, 2010 - 8:15:59 PM

### File

RR-6587.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00303330, version 1

### Citation

Frédéric Havet, Martin Klazar, Jan Kratochvil, Dieter Kratsch, Matthieu Liedloff. Exact algorithms for $L(2,1)$-labeling of graphs. [Research Report] RR-6587, INRIA. 2008. ⟨inria-00303330⟩

Record views