2,1)-labeling of graph

Speaker(s)

Konstanty Junosza-Szaniawski

Affiliation

Politechnika Warszawska

Date

Feb. 24, 2011, 12:15 p.m.

Room

room 5870

Title in Polish

Exact algorithms for L

Seminar

Seminar Algorithms

---

$L(2,1)$-labeling is a graph coloring model inspired by a channel assignment problem 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 fixed $k \geq 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 an improved 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.56^n)$ to $O^*(3.23^n)$. Moreover, we establish a lower complexity bound, which is $\Omega^{*} (3.07^n)$.

---