Exact Algorithms for L(2,1)‐Labeling of Graphs

Exact Algorithms for L(2,1)‐Labeling of Graphs

0.00 Avg rating0 Votes
Article ID: iaor20112027
Volume: 59
Issue: 2
Start Page Number: 169
End Page Number: 194
Publication Date: Feb 2011
Journal: Algorithmica
Authors: , , , ,
Keywords: programming: dynamic
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.3006 n ). Furthermore we show that dynamic programming can be used to establish an O(3.8730 n ) algorithm to compute an optimal L(2,1)‐labeling.

Reviews

Required fields are marked *. Your email address will not be published.