{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T14:44:23Z","timestamp":1772376263921,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-08554S"],"award-info":[{"award-number":["19-08554S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["413902284"],"award-info":[{"award-number":["413902284"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s00453-019-00640-2","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T22:37:06Z","timestamp":1572043026000},"page":"1239-1258","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Constant-Time Algorithm for Middle Levels Gray Codes"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6383-7436","authenticated-orcid":false,"given":"Torsten","family":"M\u00fctze","sequence":"first","affiliation":[]},{"given":"Jerri","family":"Nummenpalo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,25]]},"reference":[{"key":"640_CR1","doi-asserted-by":"crossref","unstructured":"M\u00fctze, T., Nummenpalo, J.: A constant-time algorithm for middle levels Gray codes. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319, pp. 2238\u20132253 (2017)","DOI":"10.1137\/1.9781611974782.147"},{"issue":"4","key":"640_CR2","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/S0036144595295272","volume":"39","author":"CD Savage","year":"1997","unstructured":"Savage, C.D.: A survey of combinatorial Gray codes. SIAM Rev. 39(4), 605\u2013629 (1997)","journal-title":"SIAM Rev."},{"key":"640_CR3","unstructured":"Knuth, D.E.: The Art of Computer Programming, Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ (2011)"},{"key":"640_CR4","unstructured":"Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms. Academic Press, New York-London (1975). Computer Science and Applied Mathematics"},{"key":"640_CR5","unstructured":"Wilf, H.S.: Combinatorial algorithms: an update, volume 55 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1989)"},{"key":"640_CR6","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1090\/S0025-5718-1963-0159764-2","volume":"17","author":"SM Johnson","year":"1963","unstructured":"Johnson, S.M.: Generation of permutations by adjacent transposition. Math. Comput. 17, 282\u2013285 (1963)","journal-title":"Math. Comput."},{"issue":"8","key":"640_CR7","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1145\/368637.368660","volume":"5","author":"H Trotter","year":"1962","unstructured":"Trotter, H.: Algorithm 115: Perm. Commun. ACM 5(8), 434\u2013435 (1962)","journal-title":"Commun. ACM"},{"issue":"2","key":"640_CR8","first-page":"158","volume":"15","author":"N Dershowitz","year":"1975","unstructured":"Dershowitz, N.: A simplified loop-free algorithm for generating permutations. Nordisk Tidskr. Informationsbehandling (BIT) 15(2), 158\u2013164 (1975)","journal-title":"Nordisk Tidskr. Informationsbehandling (BIT)"},{"issue":"2","key":"640_CR9","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/356689.356692","volume":"9","author":"R Sedgewick","year":"1977","unstructured":"Sedgewick, R.: Permutation generation methods. Comput. Surv. 9(2), 137\u2013164 (1977)","journal-title":"Comput. Surv."},{"key":"640_CR10","unstructured":"Gray, F.: Pulse code communication (1953). March 17 (filed Nov. 1947). U.S. Patent 2,632,058"},{"key":"640_CR11","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1145\/321765.321781","volume":"20","author":"G Ehrlich","year":"1973","unstructured":"Ehrlich, G.: Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. Assoc. Comput. Mach. 20, 500\u2013513 (1973)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"9","key":"640_CR12","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1145\/360336.360343","volume":"19","author":"J Bitner","year":"1976","unstructured":"Bitner, J., Ehrlich, G., Reingold, E.: Efficient generation of the binary reflected Gray code and its applications. Commun. ACM 19(9), 517\u2013521 (1976)","journal-title":"Commun. ACM"},{"issue":"1","key":"640_CR13","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/2422.322413","volume":"31","author":"P Eades","year":"1984","unstructured":"Eades, P., Hickey, M., Read, R.C.: Some Hamilton paths and a minimal change algorithm. J. Assoc. Comput. Mach. 31(1), 19\u201329 (1984)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"640_CR14","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(84)90091-7","volume":"19","author":"P Eades","year":"1984","unstructured":"Eades, P., McKay, B.: An algorithm for generating subsets of fixed size with a strong minimal change property. Inform. Process. Lett. 19(3), 131\u2013133 (1984)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"640_CR15","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0196-6774(88)90036-3","volume":"9","author":"F Ruskey","year":"1988","unstructured":"Ruskey, F.: Adjacent interchange generation of combinations. J. Algorithms 9(2), 162\u2013180 (1988)","journal-title":"J. Algorithms"},{"issue":"3","key":"640_CR16","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1145\/3828.214141","volume":"32","author":"D Zerling","year":"1985","unstructured":"Zerling, D.: Generating binary trees using rotations. J. Assoc. Comput. Mach. 32(3), 694\u2013701 (1985)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"640_CR17","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/0196-6774(87)90048-4","volume":"8","author":"JM Lucas","year":"1987","unstructured":"Lucas, J.M.: The rotation graph of binary trees is Hamiltonian. J. Algorithms 8(4), 503\u2013535 (1987)","journal-title":"J. Algorithms"},{"issue":"3","key":"640_CR18","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1006\/jagm.1993.1045","volume":"15","author":"JM Lucas","year":"1993","unstructured":"Lucas, J.M., Roelants van Baronaigien, D., Ruskey, F.: On rotations and the generation of binary trees. J. Algorithms 15(3), 343\u2013366 (1993)","journal-title":"J. Algorithms"},{"issue":"1","key":"640_CR19","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1109\/TCT.1966.1082546","volume":"13","author":"R. Cummins","year":"1966","unstructured":"Cummins, R.L.: Hamilton circuits in tree graphs. IEEE Trans. Circuit Theory CT-13:82\u201390 (1966)","journal-title":"IEEE Transactions on Circuit Theory"},{"issue":"3","key":"640_CR20","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1109\/TCT.1967.1082707","volume":"14","author":"T. Kamae","year":"1967","unstructured":"Kamae, T.: The existence of a Hamilton circuit in a tree graph. IEEE Trans. Circuit Theory CT-14:279\u2013283 (1967)","journal-title":"IEEE Transactions on Circuit Theory"},{"key":"640_CR21","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/0122021","volume":"22","author":"CA Holzmann","year":"1972","unstructured":"Holzmann, C.A., Harary, F.: On the tree graph of a matroid. SIAM J. Appl. Math. 22, 187\u2013193 (1972)","journal-title":"SIAM J. Appl. Math."},{"key":"640_CR22","unstructured":"Havel, I.: Semipaths in directed cubes. In: Graphs and Other Combinatorial Topics (Prague, 1982), volume 59 of Teubner-Texte Math., pages 101\u2013108. Teubner, Leipzig (1983)"},{"issue":"2\u20133","key":"640_CR23","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0012-365X(84)90179-1","volume":"48","author":"M Buck","year":"1984","unstructured":"Buck, M., Wiedemann, D.: Gray codes with restricted density. Discrete Math. 48(2\u20133), 163\u2013171 (1984)","journal-title":"Discrete Math."},{"issue":"2","key":"640_CR24","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF00337621","volume":"5","author":"HA Kierstead","year":"1988","unstructured":"Kierstead, H.A., Trotter, W.T.: Explicit matchings in the middle levels of the Boolean lattice. Order 5(2), 163\u2013171 (1988)","journal-title":"Order"},{"key":"640_CR25","volume-title":"Mathematical Puzzles: A Connoisseur\u2019s Collection","author":"P Winkler","year":"2004","unstructured":"Winkler, P.: Mathematical Puzzles: A Connoisseur\u2019s Collection. A K Peters Ltd., Natick (2004)"},{"key":"640_CR26","doi-asserted-by":"crossref","unstructured":"Diaconis, P., Graham, R.: Magical Mathematics. Princeton University Press, Princeton, NJ (2012). The mathematical ideas that animate great magic tricks, With a foreword by Martin Gardner","DOI":"10.1515\/9781400839384"},{"issue":"1","key":"640_CR27","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1090\/bull\/1553","volume":"54","author":"WT Gowers","year":"2017","unstructured":"Gowers, W.T.: Probabilistic combinatorics and the recent work of Peter Keevash. Bull. Am. Math. Soc. (N.S.) 54(1), 107\u2013116 (2017)","journal-title":"Bull. Am. Math. Soc. (N.S.)"},{"key":"640_CR28","first-page":"97","volume":"35\u2013A","author":"CD Savage","year":"1993","unstructured":"Savage, C.D.: Long cycles in the middle two levels of the Boolean lattice. Ars Combin. 35\u2013A, 97\u2013108 (1993)","journal-title":"Ars Combin."},{"issue":"1\u20133","key":"640_CR29","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0012-365X(94)00283-O","volume":"144","author":"S Felsner","year":"1995","unstructured":"Felsner, S., Trotter, W.T.: Colorings of diagrams of interval orders and $$\\alpha $$-sequences of sets. Discrete Math. 144(1\u20133), 23\u201331 (1995). Combinatorics of ordered sets (Oberwolfach, 1991)","journal-title":"Discrete Math."},{"issue":"2","key":"640_CR30","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/0097-3165(95)90091-8","volume":"70","author":"CD Savage","year":"1995","unstructured":"Savage, C.D., Winkler, P.: Monotone Gray codes and the middle levels problem. J. Combin. Theory Ser. A 70(2), 230\u2013248 (1995)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"2","key":"640_CR31","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.jcta.2003.11.004","volume":"105","author":"JR Johnson","year":"2004","unstructured":"Johnson, J.R.: Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A 105(2), 255\u2013271 (2004)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"2","key":"640_CR32","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF00337620","volume":"5","author":"D Duffus","year":"1988","unstructured":"Duffus, D., Sands, B., Woodrow, R.: Lexicographic matchings cannot form Hamiltonian cycles. Order 5(2), 149\u2013161 (1988)","journal-title":"Order"},{"issue":"2","key":"640_CR33","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/0097-3165(94)90030-2","volume":"65","author":"DA Duffus","year":"1994","unstructured":"Duffus, D.A., Kierstead, H.A., Snevily, H.S.: An explicit $$1$$-factorization in the middle of the Boolean lattice. J. Combin. Theory Ser. A 65(2), 334\u2013342 (1994)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"1","key":"640_CR34","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/s11083-005-9008-7","volume":"22","author":"P Hor\u00e1k","year":"2005","unstructured":"Hor\u00e1k, P., Kaiser, T., Rosenfeld, M., Ryj\u00e1\u010dek, Z.: The prism over the middle-levels graph is Hamiltonian. Order 22(1), 73\u201381 (2005)","journal-title":"Order"},{"issue":"12","key":"640_CR35","doi-asserted-by":"crossref","first-page":"2448","DOI":"10.1016\/j.ins.2010.02.009","volume":"180","author":"P Gregor","year":"2010","unstructured":"Gregor, P., \u0160krekovski, R.: On generalized middle-level problem. Inform. Sci. 180(12), 2448\u20132457 (2010)","journal-title":"Inform. Sci."},{"issue":"8","key":"640_CR36","doi-asserted-by":"crossref","first-page":"1832","DOI":"10.1016\/j.jcta.2012.06.005","volume":"119","author":"T M\u00fctze","year":"2012","unstructured":"M\u00fctze, T., Weber, F.: Construction of 2-factors in the middle layer of the discrete cube. J. Combin. Theory Ser. A 119(8), 1832\u20131855 (2012)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"17","key":"640_CR37","doi-asserted-by":"crossref","first-page":"5271","DOI":"10.1016\/j.disc.2007.11.010","volume":"309","author":"I Shields","year":"2009","unstructured":"Shields, I., Shields, B., Savage, C.D.: An update on the middle levels problem. Discrete Math. 309(17), 5271\u20135277 (2009)","journal-title":"Discrete Math."},{"key":"640_CR38","unstructured":"Shimada, M., Amano, K.: A note on the middle levels conjecture. \narXiv:0912.4564\n\n (September 2011)"},{"issue":"4","key":"640_CR39","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1112\/plms\/pdw004","volume":"112","author":"T M\u00fctze","year":"2016","unstructured":"M\u00fctze, T.: Proof of the middle levels conjecture. Proc. Lond. Math. Soc. 112(4), 677\u2013713 (2016)","journal-title":"Proc. Lond. Math. Soc."},{"key":"640_CR40","first-page":"12","volume":"8","author":"P Gregor","year":"2018","unstructured":"Gregor, P., M\u00fctze, T., Nummenpalo, J.: A short proof of the middle levels theorem. Discrete Anal. 8, 12 (2018)","journal-title":"Discrete Anal."},{"issue":"2","key":"640_CR41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3170443","volume":"14","author":"Torsten M\u00dcTZE","year":"2018","unstructured":"M\u00fctze, T., Nummenpalo, J.: Efficient computation of middle levels Gray codes. ACM Trans. Algorithms (TALG), 14(2):29 pp., 2018. An extended abstract appeared in the Proceedings of the European Symposium on Algorithms (ESA 2015)","journal-title":"ACM Transactions on Algorithms"},{"key":"640_CR42","unstructured":"The Combinatorial Object Server. \nhttp:\/\/combos.org"},{"key":"640_CR43","unstructured":"Simpson, J.E.: Hamiltonian bipartite graphs. In: Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Vol. 85, pp. 97\u2013110 (1991)"},{"issue":"1\u20133","key":"640_CR44","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0012-365X(94)90115-5","volume":"128","author":"G Hurlbert","year":"1994","unstructured":"Hurlbert, G.: The antipodal layers problem. Discrete Math. 128(1\u20133), 237\u2013245 (1994)","journal-title":"Discrete Math."},{"issue":"1","key":"640_CR45","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1006\/jctb.2000.1969","volume":"80","author":"Y Chen","year":"2000","unstructured":"Chen, Y.: Kneser graphs are Hamiltonian for $$n\\ge 3k$$. J. Combin. Theory Ser. B 80(1), 69\u201379 (2000)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"640_CR46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0095-8956(03)00040-6","volume":"89","author":"Y Chen","year":"2003","unstructured":"Chen, Y.: Triangle-free Hamiltonian Kneser graphs. J. Combin. Theory Ser. B 89(1), 1\u201316 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"6","key":"640_CR47","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1007\/s00493-016-3434-6","volume":"37","author":"T M\u00fctze","year":"2017","unstructured":"M\u00fctze, T., Su, P.: Bipartite Kneser graphs are Hamiltonian. Combinatorica 37(6), 1207\u20131219 (2017)","journal-title":"Combinatorica"},{"key":"640_CR48","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.tcs.2017.12.003","volume":"714","author":"P Gregor","year":"2018","unstructured":"Gregor, P., M\u00fctze, T.: Trimming and gluing Gray codes. Theoret. Comput. Sci. 714, 74\u201395 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"640_CR49","unstructured":"Herter, F., Rote, G.: Loopless Gray code enumeration and the tower of Bucharest. In: 8th International Conference on Fun with Algorithms, FUN 2016, June 8\u201310, 2016, La Maddalena, Italy, pages 19:1\u201319:19 (2016)"},{"key":"640_CR50","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.ejc.2017.11.003","volume":"69","author":"T M\u00fctze","year":"2018","unstructured":"M\u00fctze, T., Standke, C., Wiechert, V.: A minimum-change version of the Chung-Feller theorem for Dyck paths. Eur. J. Combin. 69, 260\u2013275 (2018)","journal-title":"Eur. J. Combin."},{"issue":"4\u20135","key":"640_CR51","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/0020-0190(80)90149-0","volume":"10","author":"KS Booth","year":"1980","unstructured":"Booth, K.S.: Lexicographically least circular substrings. Inform. Process. Lett. 10(4\u20135), 240\u2013242 (1980)","journal-title":"Inform. Process. Lett."},{"key":"640_CR52","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139871495","volume-title":"Catalan Numbers","author":"RP Stanley","year":"2015","unstructured":"Stanley, R.P.: Catalan Numbers. Cambridge University Press, New York (2015)"},{"key":"640_CR53","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84800-070-4","volume-title":"The Algorithm Design Manual","author":"S Skiena","year":"2008","unstructured":"Skiena, S.: The Algorithm Design Manual, 2nd edn. Springer, New York (2008)","edition":"2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00640-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00640-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00640-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T23:07:11Z","timestamp":1603494431000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00640-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,25]]},"references-count":53,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["640"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00640-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,25]]},"assertion":[{"value":"7 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}