On 15.05.2008 at 12:20, in S1, there is the following noon lecture:
Exact algorithms for Frequency Assignment: Branching versus Dynamic Programming
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
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019