Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 15.05.2008 at 12:20, in S1, there is the following noon lecture:

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

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010