Trimming and gluing Gray codes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10384203" target="_blank" >RIV/00216208:11320/18:10384203 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.tcs.2017.12.003" target="_blank" >https://doi.org/10.1016/j.tcs.2017.12.003</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2017.12.003" target="_blank" >10.1016/j.tcs.2017.12.003</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Trimming and gluing Gray codes

Popis výsledku v původním jazyce

We consider the algorithmic problem of generating each subset of [n] := {1, 2, ..., n} whose size is in some interval [k,1], 0 &lt;= k &lt;= l &lt; 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)(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 O(1) time per generated set and O(n) space. Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Qt, induced by all levels [k, I]. 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 epsilon {0, 1 ,..., k} has a Hamilton cycle. We also prove an approximate version of this generalized conjecture, showing that this graph has a cycle that visits a (1 - o(1))-fraction of all vertices.

Název v anglickém jazyce

Trimming and gluing Gray codes

Popis výsledku anglicky

We consider the algorithmic problem of generating each subset of [n] := {1, 2, ..., n} whose size is in some interval [k,1], 0 &lt;= k &lt;= l &lt; 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)(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 O(1) time per generated set and O(n) space. Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Qt, induced by all levels [k, I]. 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 epsilon {0, 1 ,..., k} has a Hamilton cycle. We also prove an approximate version of this generalized conjecture, showing that this graph has a cycle that visits a (1 - o(1))-fraction of all vertices.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

714

Číslo periodika v rámci svazku

1. března

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

22

Strana od-do

74-95

Kód UT WoS článku

000424959300006

EID výsledku v databázi Scopus

2-s2.0-85037594257