HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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

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
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

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⟩

Share

Metrics

Record views

206

Files downloads

434