The Library
A constant-time algorithm for middle levels Gray codes
Tools
Mutze, Torsten and Nummenpalo, Jerri (2017) A constant-time algorithm for middle levels Gray codes. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 16-19 Jan 2017. Published in: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) pp. 2238-2253. ISBN 9781611974782. doi:10.1137/1.9781611974782.147
|
PDF
WRAP-constant-time-algorithm-middle-levels-Gray-codes-Mutze-2017.pdf - Accepted Version - Requires a PDF viewer. Download (1063Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611974782.147
Abstract
For any integer~$n\geq 1$, a \emph{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 sets differ in adding or removing a single element.
The question whether such a Gray code exists for any~$n\geq 1$ 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. \textit{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. \textit{ACM Trans. Algorithms}, 14(2):29~pp., 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in time~$\cO(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~$\cO(1)$, and the required space is~$\cO(n)$.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Gray codes, Hamiltonian graph theory, Combinatorial analysis | ||||||
Journal or Publication Title: | Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) | ||||||
Publisher: | SIAM | ||||||
ISBN: | 9781611974782 | ||||||
Official Date: | 1 January 2017 | ||||||
Dates: |
|
||||||
Page Range: | pp. 2238-2253 | ||||||
DOI: | 10.1137/1.9781611974782.147 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 17 June 2019 | ||||||
Date of first compliant Open Access: | 17 June 2019 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Barcelona, Spain | ||||||
Date(s) of Event: | 16-19 Jan 2017 | ||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year