On the complexity of exact algorithm for L(2,1)-labeling of graphs
L(2, 1)-labeling is a graph coloring model inspired by a frequency assignment in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. It is known that for any k >= 4 it is NP-complete to determine if a graph has a L(2, 1)-labeling with no label greater than k. In this paper we present a new bound on complexity of an algorithm for finding an optimal L(2, 1)-labeling (i.e. an L(2, 1)-labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from O*(3.5616(n)) to O*(3.2361(n)). Moreover, we establish a lower complexity bound of the presented algorithm, which is Omega*(3.0739(n)). (C) 2011 Elsevier B.V. All rights reserved.
exact algorithm l(2,1)-labeling graph coloring model analysis of algorithms combinatorial problems graph algorithms