Exact algorithms for Frequency Assignment: Branching versus Dynamic Programming

Jan Kratochvíl

KAM

Abstract

One thoroughly studied model of the Frequency Assignment Problem is the distance-constrained graph labeling. In particular, an L(2,1)-labeling of a graph is a labeling of its vertices by nonnegative integers such that the labels of adjacent vertices differ by at least 2, and every two vertices with a common neighbor receive different labels. This problem exhibits a remarkably different behavior than ordinary graph coloring - a linear time algorithm for trees is an open problem, and it becomes NP-complete already for graphs of tree-width 2.

In this talk we show two methods for constructing exact, exponential time algorithms with the base in the exponential function as small as possible. One is a dynamic programming based algorithm for determining the smallest possible span that runs in time $O^*(c^n)$ for a constant c<4. The other is a branching algorithm that decides if a graph