A constant-time algorithm for middle levels Gray codes

DOI10.1137/1.9781611974782.147zbMATH Open1414.94946arXiv1606.06172OpenAlexW2471996798MaRDI QIDQ4575895FDOQ4575895

Authors: Torsten Mütze, Jerri Nummenpalo 

Publication date: 16 July 2018

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

Abstract: For any integer $ngeq1$ a middle levels Gray code is a cyclic listing of all $n$-element and $(n+1)$-element subsets of $1,2,ldots,2n+1$ such that any two consecutive subsets differ in adding or removing a single element. The question whether such a Gray code exists for any $ngeq1$ has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. M"utze. Proof of the middle levels conjecture. Proc. London Math. Soc., 112(4):677--713, 2016]. In a follow-up paper [T. M"utze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. To appear in ACM Transactions on Algorithms, 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in time $mathcalO(n)$ on average. In this work we present an algorithm for computing a middle levels Gray code in optimal time and space: each new set is generated in time $mathcalO(1)$ on average, and the required space is $mathcalO(n)$.

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

Recommendations

• A constant-time algorithm for middle levels Gray codes
• Efficient Computation of Middle Levels Gray Codes
• Efficient computation of middle levels Gray codes
• Trimming and gluing Gray codes
• Trimming and gluing Gray codes

Mathematics Subject Classification ID

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

Cited In (15)

• Space-optimal quasi-Gray codes with logarithmic read complexity
• Efficient Computation of Middle Levels Gray Codes
• Loopless Gray code enumeration and the Tower of Bucharest
• A minimum-change version of the Chung-Feller theorem for Dyck paths
• A minimum-change version of the Chung-Feller theorem for Dyck paths
• Two algorithms extending a perfect matching of the hypercube into a Hamiltonian cycle
• Gray codes and symmetric chains
• Towards a problem of Ruskey and Savage on matching extendability
• Efficient computation of middle levels Gray codes
• On 1-factorizations of bipartite Kneser graphs
• Trimming and gluing Gray codes
• Trimming and gluing Gray codes
• On the central levels problem
• A constant-time algorithm for middle levels Gray codes
• A short proof of the middle levels theorem

This page was built for publication: A constant-time algorithm for middle levels Gray codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575895)