{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T19:30:31Z","timestamp":1773171031977,"version":"3.50.1"},"reference-count":86,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T00:00:00Z","timestamp":1734393600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANID Becas Chile","award":["2019-72200522"],"award-info":[{"award-number":["2019-72200522"]}]},{"name":"European Unions Horizon 2020 research and innovation programme","award":["850979"],"award-info":[{"award-number":["850979"]}]},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["GA 19-08554S"],"award-info":[{"award-number":["GA 19-08554S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"German Science Foundation","award":["413902284"],"award-info":[{"award-number":["413902284"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"\n An elimination tree for a connected graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is a rooted tree on the vertices of\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n obtained by choosing a root\n \n \\(x\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and recursing on the connected components of\n \n \\(G-x\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n to produce the subtrees of\n \n \\(x\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Elimination trees appear in many guises in computer science and discrete mathematics, and they encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung\u2013Hoang\u2013M\u00fctze\u2013Williams combinatorial generation framework to elimination trees and prove that all elimination trees for a chordal graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n can be generated by tree rotations using a simple greedy algorithm. This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n can be implemented in time\n \n \\({\\mathcal{O}}(\\sigma)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n on average per generated elimination tree, where\n \n \\(\\sigma=\\sigma(G)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denotes the maximum number of edges of an induced star in\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . If\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is a tree, we improve this to a loopless algorithm running in time\n \n \\({\\mathcal{O}}(1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , rather than just Hamilton path, if the graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n if and only if\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is chordal.\n <\/jats:p>","DOI":"10.1145\/3689633","type":"journal-article","created":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T05:03:43Z","timestamp":1730437423000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Combinatorial Generation via Permutation Languages. IV. Elimination Trees"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2312-0967","authenticated-orcid":false,"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[{"name":"Computer Science Department, Universit\u00e9 Libre de Bruxelles (ULB), Bruxelles, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1728-6936","authenticated-orcid":false,"given":"Arturo","family":"Merino","sequence":"additional","affiliation":[{"name":"Instituto de Ciencias de la Ingenier\u00eda, Universidad de O\u2019Higgins, Rancagua, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6383-7436","authenticated-orcid":false,"given":"Torsten","family":"M\u00fctze","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Warwick, Coventry, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,17]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"263","article-title":"An algorithm for organization of information","volume":"146","author":"Adel\u2019son-Vel\u2019ski\u012d G. M.","year":"1962","unstructured":"G. M. Adel\u2019son-Vel\u2019ski\u012d and E. M. Landis. 1962. An algorithm for organization of information. Dokl. Akad. Nauk SSSR 146 (1962), 263\u2013266.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/1437"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934264"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1080\/10236199908808200"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-020-00689-z"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979731858X"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.4310\/JOC.2019.v10.n3.a4"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/lipics.swat.2022.14"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.75"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195282550"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.115"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.37236\/7762"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.84"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-022-00598-z"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.topol.2005.08.010"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1108"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00221-4"},{"key":"e_1_3_1_21_2","unstructured":"Combos. 2024. The Combinatorial Object Server: Generate Elimination Trees. Retrieved from http:\/\/www.combos.org\/elim"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57785-8_187"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00179-1"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.092"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/321765.321781"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/S089547980240563X"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/050643581"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897656"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9914-4"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0893-9659(94)90045-0"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"e_1_3_1_33_2","unstructured":"F. Gray. 1953. Pulse code communication. (Mar. 1953). U.S. Patent 2 632 058. Filed Nov. 1947."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_3_1_35_2","author":"Harary F.","year":"1973","unstructured":"F. Harary and E. M. Palmer. 1973. Graphical Enumeration. Academic Press, New York-London. xiv+271 p.","journal-title":"Graphical Enumeration"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/8199"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-021-2186-1"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-1319-6"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00016-4"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90194-9"},{"key":"e_1_3_1_41_2","volume-title":"Parallel Assembly of Modular Products","author":"Iyer A. V.","year":"1988","unstructured":"A. V. Iyer, H. D. Ratliff, and G. Vijayan. 1988b. Parallel Assembly of Modular Products. Technical Report 88-06. Technical Report. Production and Distribution Research Center, Georgia Institute of Technology, Atlanta, GA."},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90012-L"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1963-0159764-2"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.17"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90014-4"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/1984890"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.13"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.007"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/0909029"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/66888.66890"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00013-004-1026-y"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1045"},{"key":"e_1_3_1_54_2","first-page":"31","article-title":"Graph properties of graph associahedra","volume":"73","author":"Manneville T.","year":"2015","unstructured":"T. Manneville and V. Pilaud. 2015. Graph properties of graph associahedra. S\u00e9m. Lothar. Combin. 73 (2015), Art. B73d, 31 pp.","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/227\/03259"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00393-w"},{"key":"e_1_3_1_57_2","first-page":"1096","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Mozes S.","year":"2008","unstructured":"S. Mozes, K. Onak, and O. Weimann. 2008. Finding an optimal tree searching strategy in linear time. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, NY, 1096\u20131105."},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_1_59_2","volume-title":"Concurrent Design of Products and Processes","author":"Nevins J. L.","year":"1989","unstructured":"J. L. Nevins and D. E. Whitney (Eds.). 1989. Concurrent Design of Products and Processes. McGraw-Hill."},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.32"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12231"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnn153"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.4171\/dm\/248"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.02.035"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1492-0"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01110545"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791202647"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_77"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_732"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.07.005"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144595295272"},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90161-0"},{"key":"e_1_3_1_74_2","first-page":"159","volume-title":"Proceedings of the 3rd Twente Workshop on Graphs and Combinatorial Optimization","author":"Scheffler P.","year":"1993","unstructured":"P. Scheffler. 1993. Node ranking and searching on graphs. In Proceedings of the 3rd Twente Workshop on Graphs and Combinatorial Optimization, 159\u2013162."},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90017-P"},{"key":"e_1_3_1_76_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(02)00522-5"},{"key":"e_1_3_1_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_3_1_78_2","doi-asserted-by":"publisher","DOI":"10.2307\/1990951"},{"key":"e_1_3_1_79_2","volume-title":"Generating Spanning Trees","author":"Smith M. J.","year":"1997","unstructured":"M. J. Smith. 1997. Generating Spanning Trees. Master\u2019s thesis. University of Victoria."},{"key":"e_1_3_1_80_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139871495"},{"key":"e_1_3_1_81_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(86)90071-4"},{"key":"e_1_3_1_82_2","first-page":"174","volume-title":"One Hundred Problems in Elementary Mathematics","author":"Steinhaus H.","year":"1964","unstructured":"H. Steinhaus. 1964. One Hundred Problems in Elementary Mathematics. Basic Books, Inc., New York. 174 p."},{"key":"e_1_3_1_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/368637.368660"},{"key":"e_1_3_1_84_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206036"},{"key":"e_1_3_1_85_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.1.83"},{"key":"e_1_3_1_86_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_46"},{"key":"e_1_3_1_87_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582944"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689633","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:47Z","timestamp":1750295387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,17]]},"references-count":86,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3689633"],"URL":"https:\/\/doi.org\/10.1145\/3689633","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,17]]},"assertion":[{"value":"2021-10-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}