TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Publications

COGA 5-Wheel

Page Content

to Navigation

List of all publications

Gray codes and symmetric chains
Citation key GregorJaegerMuetze+2018
Author Gregor, Petr and Jäger, Sven and Mütze, Torsten and Sawada, Joe and Wille, Kaja
Title of Book 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Pages 66:1–66:14
Year 2018
ISBN 978-3-95977-076-7
ISSN 1868-8969
DOI 10.4230/LIPIcs.ICALP.2018.66
Location Prague
Address Dagstuhl, Germany
Volume 107
Month 7
Editor Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, Dániel and Sannella, Donald
Publisher Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
Series Leibniz International Proceedings in Informatics (LIPIcs)
Abstract We consider the problem of constructing a cyclic listing of all bitstrings of length 2n+1 with Hamming weights in the interval [n+1-l,n+l], where 1 <= l <= n+1, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (l=1). We provide a solution for the case l=2 and solve a relaxed version of the problem for general values of l, by constructing cycle factors for those instances. Our proof uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets, and we present several new constructions of such decompositions. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-dimensional hypercube for any n >= 12.
Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe