Trimming and gluing gray codes
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10367480" target="_blank" >RIV/00216208:11320/17:10367480 - isvavai.cz</a>
Result on the web
<a href="http://drops.dagstuhl.de/opus/volltexte/2017/6993" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2017/6993</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2017.40" target="_blank" >10.4230/LIPIcs.STACS.2017.40</a>
Alternative languages
Result language
angličtina
Original language name
Trimming and gluing gray codes
Original language description
We consider the algorithmic problem of generating each subset of [n]:={1,2,...,n} whose size is in some interval [k,l], 0 <= k <= l <= n, exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k=0 and l=n this is the classical problem of generating all 2^n subsets of [n] by element additions/removals, and for k=l this is the classical problem of generating all n over k subsets of [n] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n, k, and l, improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant time O(1) per generated set and space O(n). Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Q_n induced by all levels [k,l]. We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q_(2k+1) induced by all levels [k-c,k+1+c], c in {0, 1, ... , k}, has a Hamilton cycle. We also prove an approximate version of this conjecture, showing that this graph has a cycle that visits a (1-o(1))-fraction of all vertices.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA14-10799S" target="_blank" >GA14-10799S: Hybercubic, graph and hypergraph structures</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-028-6
ISSN
1868-8969
e-ISSN
neuvedeno
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Place of publication
Dagstuhl, Germany
Event location
Hannover
Event date
Mar 8, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—