Colloquium Details
Exact algorithms for Frequency Assignment: Branching versus Dynamic Programming
| Author: | Jan Kratochvil Charles University, Prague |
|---|---|
| Date: | April 14, 2008 |
| Time: | 13:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
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 has an L(2,1)-labeling of span 4 in time $O^*(1,31^n)$. The advantage of the latter is that it needs only polynomial space. In both cases we beat the previously known bounds considerably.
The talk is based on a joint paper with F. Havet, M. Klazar, D. Kratsch and M. Liedlof.
Biography
Jan Kratochvil is a full professor and head of the Department of Applied Mathematics at Charles University in Prague, Czech Republic. His major area of work is theoretical computer science, in particular algorithms and complexity in graph theory. He received his Ph.D. at Charles University in 1987 for a thesis about domination and codes in graphs.