A constant-time algorithm for middle levels Gray codes

DOI10.1137/1.9781611974782.147zbMath1414.94946arXiv1606.06172OpenAlexW2471996798MaRDI QIDQ4575895

Jerri Nummenpalo, Torsten Mütze

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.06172

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial codes (94B25)

Related Items

Loopless Gray code enumeration and the Tower of Bucharest ⋮ Two algorithms extending a perfect matching of the hypercube into a Hamiltonian cycle ⋮ Towards a problem of Ruskey and Savage on matching extendability ⋮ Trimming and gluing Gray codes ⋮ Unnamed Item ⋮ On the central levels problem ⋮ Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity ⋮ A short proof of the middle levels theorem ⋮ A minimum-change version of the Chung-Feller theorem for Dyck paths ⋮ On 1-factorizations of bipartite Kneser graphs ⋮ A constant-time algorithm for middle levels Gray codes ⋮ A minimum-change version of the Chung-Feller theorem for Dyck paths