{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:57:01Z","timestamp":1742929021450,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":37,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819705658"},{"type":"electronic","value":"9789819705665"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-97-0566-5_9","type":"book-chapter","created":{"date-parts":[[2024,2,28]],"date-time":"2024-02-28T12:03:28Z","timestamp":1709121808000},"page":"103-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Hardness of\u00a0Gray Code Problems for\u00a0Combinatorial Objects"],"prefix":"10.1007","author":[{"given":"Arturo","family":"Merino","sequence":"first","affiliation":[]},{"family":"Namrata","sequence":"additional","affiliation":[]},{"given":"Aaron","family":"Williams","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,29]]},"reference":[{"issue":"14","key":"9_CR1","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1016\/j.ipl.2009.03.025","volume":"109","author":"J-L Baril","year":"2009","unstructured":"Baril, J.-L.: More restrictive gray codes for some classes of pattern avoiding permutations. Inf. Process. Lett. 109(14), 799\u2013804 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"2\u20133","key":"9_CR2","doi-asserted-by":"publisher","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. Discret. Math. 48(2\u20133), 163\u2013171 (1984)","journal-title":"Discret. Math."},{"issue":"3\u20134","key":"9_CR3","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1080\/03081089308818261","volume":"35","author":"RC Compton","year":"1993","unstructured":"Compton, R.C., Williamson, S.G.: Doubly adjacent gray codes for the symmetric group. Linear Multilinear Algebra 35(3\u20134), 237\u2013293 (1993)","journal-title":"Linear Multilinear Algebra"},{"issue":"05","key":"9_CR4","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1109\/71.159045","volume":"3","author":"PF Corbett","year":"1992","unstructured":"Corbett, P.F.: Rotator graphs: an efficient topology for point-to-point multiprocessor networks. IEEE Trans. Parallel Distrib. Syst. 3(05), 622\u2013626 (1992)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9_CR5","unstructured":"Demaine, E.D., Eisenstat, S., Rudoy, M.: Solving the rubik\u2019s cube optimally is NP-complete. In: STACS 2018, pp. 24:1\u201324:13 (2018)"},{"key":"9_CR6","unstructured":"Duckworth, R., Stedman, F.: Tintinnalogia: Or, The Art of Ringing. London (1668)"},{"issue":"1\u20133","key":"9_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2007.12.002","volume":"396","author":"WMB Dukes","year":"2008","unstructured":"Dukes, W.M.B., Flanagan, M.F., Mansour, T., Vajnovszki, V.: Combinatorial gray codes for classes of pattern avoiding permutations. Theor. Comput. Sci. 396(1\u20133), 35\u201349 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9_CR8","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(84)90091-7","volume":"19","author":"P Eades","year":"1984","unstructured":"Eades, P., McKay, B.D.: An algorithm for generating subsets of fixed size with a strong minimal change property. Inf. Process. Lett. 19(3), 131\u2013133 (1984)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9_CR9","doi-asserted-by":"publisher","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. ACM (JACM) 20(3), 500\u2013513 (1973)","journal-title":"J. ACM (JACM)"},{"key":"9_CR10","unstructured":"Gray, F.: Pulse code communication. United States Patent Number 2632058 (1953)"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.jctb.2022.12.008","volume":"160","author":"P Gregor","year":"2023","unstructured":"Gregor, P., Mi\u010dka, O., M\u00fctze, T.: On the central levels problem. J. Comb. Theory. Ser. B 160, 163\u2013205 (2023)","journal-title":"J. Comb. Theory. Ser. B"},{"issue":"04","key":"9_CR12","doi-asserted-by":"publisher","first-page":"2255","DOI":"10.1090\/tran\/8199","volume":"375","author":"E Hartung","year":"2022","unstructured":"Hartung, E., Hoang, H., M\u00fctze, T., Williams, A.: Combinatorial generation via permutation languages. I. fundamentals. Trans. Am. Math. Soc. 375(04), 2255\u20132291 (2022)","journal-title":"Trans. Am. Math. Soc."},{"issue":"4","key":"9_CR13","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676\u2013686 (1982)","journal-title":"SIAM J. Comput."},{"issue":"83","key":"9_CR14","doi-asserted-by":"publisher","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(83), 282\u2013285 (1963)","journal-title":"Math. Comput."},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems, complexity of computer computations (re miller and jw thatcher, editors) (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9_CR16","unstructured":"Knuth, D.E.: The Art of Computer Programming: Combinatorial Algorithms, Part 1. Addison-Wesley Professional (2011)"},{"key":"9_CR17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-031-43980-3_26","volume-title":"SPIRE 2023","author":"Z Lipt\u00e1k","year":"2023","unstructured":"Lipt\u00e1k, Z., Masillo, F., Navarro, G., Williams, A.: Constant time and space updates for the sigma-tau problem. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds.) SPIRE 2023. LNCS, vol. 14240, pp. 323\u2013330. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-43980-3_26"},{"issue":"3","key":"9_CR18","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1137\/20M1377394","volume":"51","author":"A Merino","year":"2022","unstructured":"Merino, A., Mi\u010dka, O., M\u00fctze, T.: On a combinatorial generation problem of knuth. SIAM J. Comput. 51(3), 379\u2013423 (2022)","journal-title":"SIAM J. Comput."},{"key":"9_CR19","unstructured":"Merino, A., M\u00fctze, T.: Traversing combinatorial 0\/1-polytopes via optimization. arXiv preprint arXiv:2304.08567"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Merino, A., M\u00fctze, T., Namrata: Kneser graphs are hamiltonian. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 963\u2013970 (2023)","DOI":"10.1145\/3564246.3585137"},{"key":"9_CR21","unstructured":"Merino, A., M\u00fctze, T., Williams, A.: All your bases are belong to us: listing all bases of a matroid by greedy exchanges. In: 11th International Conference on Fun with Algorithms, FUN 2022 (2022)"},{"issue":"4","key":"9_CR22","doi-asserted-by":"publisher","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":"9_CR23","doi-asserted-by":"crossref","unstructured":"M\u00fctze, T.: Combinatorial gray codes-an updated survey. arXiv preprint arXiv:2202.01280 (2022)","DOI":"10.37236\/11023"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"M\u00fctze, T.: A book proof of the middle levels theorem. arXiv preprint arXiv:2306.13019 (2023)","DOI":"10.1007\/s00493-023-00070-3"},{"issue":"1","key":"9_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0095-8956(84)90043-1","volume":"37","author":"DJ Naddef","year":"1984","unstructured":"Naddef, D.J., Pulleyblank, W.R.: Hamiltonicity in $$(0$$-$$1)$$-polyhedra. J. Combin. Theory Ser. B 37(1), 41\u201352 (1984)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"7","key":"9_CR26","first-page":"452","volume":"10","author":"RJ Ord-Smith","year":"1967","unstructured":"Ord-Smith, R.J.: Algorithm 308: generation of the permutations in pseudo-lexicographic order. Commun. ACM 10(7), 452 (1967)","journal-title":"Commun. ACM"},{"key":"9_CR27","unstructured":"Ruskey, F.: Combinatorial generation. Preliminary draft, University of Victoria (2003)"},{"issue":"17","key":"9_CR28","doi-asserted-by":"publisher","first-page":"5305","DOI":"10.1016\/j.disc.2007.11.048","volume":"309","author":"F Ruskey","year":"2009","unstructured":"Ruskey, F., Williams, A.: The coolest way to generate combinations. Discret. Math. 309(17), 5305\u20135320 (2009)","journal-title":"Discret. Math."},{"issue":"4","key":"9_CR29","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/S0036144595295272","volume":"39","author":"C Savage","year":"1997","unstructured":"Savage, C.: A survey of combinatorial gray codes. SIAM Rev. 39(4), 605\u2013629 (1997)","journal-title":"SIAM Rev."},{"issue":"1","key":"9_CR30","first-page":"1","volume":"16","author":"J Sawada","year":"2019","unstructured":"Sawada, J., Williams, A.: Solving the sigma-tau problem. ACM Trans. Algorithms (TALG) 16(1), 1\u201317 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"Shen, X.S., Williams, A.: A \u2018hot potato\u2019 gray code for permutations. Electron. Notes Discrete Math. 44, 89\u201394 (2013)","DOI":"10.1016\/j.endm.2013.10.014"},{"key":"9_CR32","unstructured":"Smith, M.J.: Generating spanning trees (1997)"},{"key":"9_CR33","unstructured":"Steinhaus, H.: One hundred problems in elementary mathematics (1979)"},{"key":"9_CR34","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s00224-013-9486-8","volume":"54","author":"B Stevens","year":"2014","unstructured":"Stevens, B., Williams, A.: The coolest way to generate binary strings. Theory Comput. Syst. 54, 551\u2013577 (2014)","journal-title":"Theory Comput. Syst."},{"key":"9_CR35","unstructured":"Stibitz, G.R.: Binary counter. United States Patent Number 2307868 (1943)"},{"issue":"2","key":"9_CR36","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1109\/T-C.1973.223681","volume":"100","author":"DT Tang","year":"1973","unstructured":"Tang, D.T., Liu, C.N.: Distance-2 cyclic chaining of constant-weight codes. IEEE Trans. Comput. 100(2), 176\u2013180 (1973)","journal-title":"IEEE Trans. Comput."},{"issue":"8","key":"9_CR37","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1145\/368637.368660","volume":"5","author":"HF Trotter","year":"1962","unstructured":"Trotter, H.F.: Algorithm 115: perm. Commun. ACM 5(8), 434\u2013435 (1962)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-0566-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T16:08:14Z","timestamp":1709654894000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-0566-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819705658","9789819705665"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-0566-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"29 February 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kanazawa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 March 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 March 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.walcom-conference.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"80","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}