Fast exact algorithm forL(2,1)-labeling of graphs

• DOI: 10.1016/j.tcs.2012.06.037
• Publication Date: 2012-07-10T16:50:54Z
• Authors: Konstanty Junosza...; Jan Kratochvíl; Mathieu Liedloff; Peter Rossmanith; Paweł Rzążewski
• Keywords: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]; 0211 other engineering and technologies; 02 engineering and technology; 0102 computer and information sciences; 01 natural sciences

An L(2,1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L(2,1)-span of a graph is the minimum possible span of its L(2,1)-labelings. We show how to compute the L(2,1)-span of a connected graph in time O^*(2.6488^n). Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O^*(2.5944^n) for claw-free graphs, and in time O^*(2^n^-^r(2+nr)^r) for graphs having a dominating set of size r.