{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:36:24Z","timestamp":1750221384729,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T00:00:00Z","timestamp":1523836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>\n            For any integer\n            <jats:italic>n<\/jats:italic>\n            \u2265 1, a\n            <jats:italic>middle levels Gray code<\/jats:italic>\n            is a cyclic listing of all bitstrings of length 2\n            <jats:italic>n<\/jats:italic>\n            +1 that have either\n            <jats:italic>n<\/jats:italic>\n            or\n            <jats:italic>n<\/jats:italic>\n            +1 entries equal to 1 such that any two consecutive bitstrings in the list differ in exactly one bit. The question whether such a Gray code exists for every\n            <jats:italic>n<\/jats:italic>\n            \u2265 1 has been the subject of intensive research during the past 30 years and has been answered affirmatively only recently [T.\u00a0M\u00fctze. Proof of the middle levels conjecture.\n            <jats:italic>Proc. London Math. Soc.<\/jats:italic>\n            , 112(4):677--713, 2016]. In this work, we provide the first efficient algorithm to compute a middle levels Gray code. For a given bitstring, our algorithm computes the next \u2113 bitstrings in the Gray code in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u2113 (1+\n            <jats:italic>n<\/jats:italic>\n            \/\u2113)), which is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) on average per bitstring provided that \u2113 = \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3170443","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T17:21:50Z","timestamp":1524072110000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Computation of Middle Levels Gray Codes"],"prefix":"10.1145","volume":"14","author":[{"given":"Torsten","family":"M\u00dcTZE","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Institute of Mathematics, Berlin, Germany"}]},{"given":"Jerri","family":"Nummenpalo","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Department of Computer Science, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360336.360343"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90179-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.03.068"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1966.1082546"},{"key":"e_1_2_1_5_1","unstructured":"P. Diaconis and R. Graham. 2012. Magical Mathematics. Princeton University Press Princeton NJ.  P. Diaconis and R. Graham. 2012. Magical Mathematics. Princeton University Press Princeton NJ."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(94)90030-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00337620"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322413"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90091-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321765.321781"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00283-O"},{"key":"e_1_2_1_12_1","first-page":"632","article-title":"Pulse code communication (filed Nov. 1947)","volume":"2","author":"Gray F.","year":"1953","unstructured":"F. Gray . 1953 . Pulse code communication (filed Nov. 1947) . U.S. Patent 2 , 632 ,058. F. Gray. 1953. Pulse code communication (filed Nov. 1947). U.S. Patent 2,632,058.","journal-title":"U.S. Patent"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.02.009"},{"key":"e_1_2_1_14_1","volume-title":"Graphs and Other Combinatorial Topics (Prague","volume":"59","author":"Havel I.","year":"1983","unstructured":"I. Havel . 1983 . Semipaths in directed cubes . In Graphs and Other Combinatorial Topics (Prague , 1982). Teubner-Texte Math. , Vol. 59 . Teubner, Leipzig, 101--108. I. Havel. 1983. Semipaths in directed cubes. In Graphs and Other Combinatorial Topics (Prague, 1982). Teubner-Texte Math., Vol. 59. Teubner, Leipzig, 101--108."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0122021"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-005-9008-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2003.11.004"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1963-0159764-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00337621"},{"key":"e_1_2_1_20_1","unstructured":"D. Knuth. 2011. The Art of Computer Programming Volume 4A. Addison-Wesley.   D. Knuth. 2011. The Art of Computer Programming Volume 4A. Addison-Wesley."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90048-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1045"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdw004"},{"volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"M\u00fctze T.","key":"e_1_2_1_24_1","unstructured":"T. M\u00fctze and J. Nummenpalo . 2017. A constant-time algorithm for middle levels gray codes . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) . 2238--2253. T. M\u00fctze and J. Nummenpalo. 2017. A constant-time algorithm for middle levels gray codes. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). 2238--2253."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.06.005"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90036-3"},{"key":"e_1_2_1_27_1","volume-title":"Long cycles in the middle two levels of the Boolean lattice. Ars Combin. 35-A","author":"Savage C.","year":"1993","unstructured":"C. Savage . 1993. Long cycles in the middle two levels of the Boolean lattice. Ars Combin. 35-A ( 1993 ), 97--108. C. Savage. 1993. Long cycles in the middle two levels of the Boolean lattice. Ars Combin. 35-A (1993), 97--108."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144595295272"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90091-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/356689.356692"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer. 140","author":"Shields I.","year":"1999","unstructured":"I. Shields and C. Savage . 1999. A Hamilton path heuristic with applications to the middle two levels problem . In Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer. 140 ( 1999 ), 161--178. I. Shields and C. Savage. 1999. A Hamilton path heuristic with applications to the middle two levels problem. In Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer. 140 (1999), 161--178."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.11.010"},{"key":"e_1_2_1_33_1","unstructured":"M. Shimada and K. Amano. 2011. A Note on the Middle Levels Conjecture. arXiv:0912.4564.  M. Shimada and K. Amano. 2011. A Note on the Middle Levels Conjecture. arXiv:0912.4564."},{"volume-title":"Cambridge Studies in Advanced Mathematics","author":"Stanley R.","key":"e_1_2_1_34_1","unstructured":"R. Stanley . 1999. Enumerative Combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics , Vol. 62 . Cambridge University Press , Cambridge . R. Stanley. 1999. Enumerative Combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics, Vol. 62. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/368637.368660"},{"key":"e_1_2_1_36_1","unstructured":"Currently. http:\/\/www.math.tu-berlin.de\/&sim;muetze and http:\/\/people.inf.ethz.ch\/njerri.  Currently. http:\/\/www.math.tu-berlin.de\/&sim;muetze and http:\/\/people.inf.ethz.ch\/njerri."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170443","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3170443","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:57Z","timestamp":1750213617000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170443"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,16]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3170443"],"URL":"https:\/\/doi.org\/10.1145\/3170443","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,4,16]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}