Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Mittagsseminar Talk Information |
Date and Time: Monday, February 29, 2016, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Torsten Mütze (TU Berlin)
Efficiently generating all objects in a particular combinatorial class (e.g. subsets, permutations, partitions, strings, trees, triangulations etc.) in such a way that each object is generated exactly once is one of the oldest and most fundamental problems in the area of combinatorial algorithms, and such generation algorithms are used as core building blocks in a wide range of practical applications. In this talk I present a new combinatorial Gray code and a corresponding time- and space-optimal algorithm for generating balanced combinations, i.e., all k-element subsets of {1,2,...,2k}, strengthening the classical Chung-Feller theorem. On a computer, balanced combinations are naturally represented by bitstrings of length 2k with exactly k many 1-bits, and thus encode a vast collection of Catalan-type objects such as Dyck paths, ordered trees, binary trees, triangulations etc. As an application of our results we construct cycle-factors in the odd graph and the middle levels graph --- two intensively studied families of highly symmetric graphs --- that consist of cycles of the same length.
This is joint work with Christoph Standke and Veit Wiechert.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2025 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.4803M | admin login