Noon lecture

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

On 01.12.2016 at 12:20 in S6, there is the following noon lecture:

Trimming and gluing Gray codes

Torsten Mütze

Abstract

(joint work with Petr Gregor)

We consider the algorithmic problem of generating each subset of [n]:={1,2,...,n} whose size is in some interval [a,b], 0<=a<=b<=n, exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For a=0 and b=n this is the classical problem of generating all 2^n subsets of [n] by element additions/removals, and for a=b this is the classical problem of generating all \binom{n}{a} subsets of [n] by element exchanges. In graph theoretical terms, we ask for the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Q_n induced by all levels [a,b]. We prove the existence of such cycles for a large range of values n, a, and b, and provide corresponding optimal generation algorithms, improving upon and generalizing several previous results.

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