Exact algorithms for L

Prelegent(ci)

Konstanty Junosza-Szaniawski

Afiliacja

Politechnika Warszawska

Termin

24 lutego 2011 12:15

Pokój

p. 5870

Tytuł w języku angielskim

2,1)-labeling of graph

Seminarium

Seminarium "Algorytmika"

---

$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)$.

---