The Library
Gray codes and symmetric chains
Tools
Gregor, Petr, Jager, Sven, Mutze, Torsten, Sawada, Joe and Wille, Kaja (2018) Gray codes and symmetric chains. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP), Prague, 9-13 Jul 2018. Published in: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), 107 66:1-66:14. ISBN 9783959770767. ISSN 1868-8969.
|
PDF
WRAP-Gray-codes-Mutze-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (651Kb) | Preview |
Official URL: http://drops.dagstuhl.de/opus/volltexte/2018/9070/
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-\ell,n+\ell]$, where $1\leq \ell\leq n+1$, by flipping a single bit in each step.
This is a far-ranging generalization of the well-known middle two levels problem (the case~$\ell=1$).
We provide a solution for the case~$\ell=2$ and solve a relaxed version of the problem for general values of~$\ell$, 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\geq 12$.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Hypercube, Hamiltonian graph theory, Gray codes, Partially ordered sets | ||||
Journal or Publication Title: | Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) | ||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||
ISBN: | 9783959770767 | ||||
ISSN: | 1868-8969 | ||||
Official Date: | 13 July 2018 | ||||
Dates: |
|
||||
Volume: | 107 | ||||
Page Range: | 66:1-66:14 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Date of first compliant deposit: | 17 June 2019 | ||||
Date of first compliant Open Access: | 25 June 2019 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 45th International Colloquium on Automata, Languages, and Programming (ICALP) | ||||
Type of Event: | Conference | ||||
Location of Event: | Prague | ||||
Date(s) of Event: | 9-13 Jul 2018 | ||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year