Noon lecture

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

On 08.03.2007 at 12:20 in S5, there is the following noon lecture:

Exact algorithms for generalized domination

Jan Kratochvil

KAM, MFF UK

Abstract

Let $\sigma$ and $\varrho$ be two sets of nonnegative integers. A vertex subset $S\subseteq V$ of an undirected graph $G=(V,E)$ is called a $(\sigma,\varrho)$-dominating set of $G$ if $|N(v)\cap S| \in \sigma$ for all $v\in S$ and $|N(v)\cap S| \in \varrho$ for all $v\in V\setminus S$. This notion introduced by J. A. Telle generalizes many domination-type graph invariants.

We show a general algorithm enumerating all $(\sigma,\varrho)$-dominating sets of an input graph $G$ in time $O^*(c^n)$ for some $c<2$ using only polynomial space, if $\sigma$ is successor-free, i.e., it does not contain two consecutive integers, and either both $\sigma$ and $\varrho$ are finite, or one of them is finite and $\sigma \cap \varrho = \emptyset$. Thus in this case one can find maximum and minimum $(\sigma,\varrho)$-dominating setsin time $o(2^n)$, though for many particular choices of $\sigma$ and $\varrho$ already the

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