License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.40
URN: urn:nbn:de:0030-drops-69930
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6993/
Go to the corresponding LIPIcs Volume Portal

Gregor, Petr ; Mütze, Torsten

Trimming and Gluing Gray Codes

pdf-format:
LIPIcs-STACS-2017-40.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{gregor_et_al:LIPIcs:2017:6993,
  author =	{Petr Gregor and Torsten M{\"u}tze},
  title =	{{Trimming and Gluing Gray Codes}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6993},
  URN =		{urn:nbn:de:0030-drops-69930},
  doi =		{10.4230/LIPIcs.STACS.2017.40},
  annote =	{Keywords: Gray code, subset, combination, loopless algorithm}
}

Keywords: Gray code, subset, combination, loopless algorithm
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI