{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:49Z","timestamp":1787322889652,"version":"build-2736575974"},"reference-count":48,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Agencia Nacional de Investagacion y Desarrollo","award":["2019-72200522"],"award-info":[{"award-number":["2019-72200522"]}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["GA 22-15272S"],"award-info":[{"award-number":["GA 22-15272S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provide two generalizations of this result. First, we describe Gray codes for acyclic orientations of hypergraphs that satisfy a simple ordering condition, which generalizes the notion of perfect elimination order of graphs. This unifies the Savage\u2013Squire\u2013West construction with a recent algorithm for generating elimination trees of chordal graphs. Second, we consider quotients of lattices of acyclic orientations of chordal graphs, and we provide a Gray code for them, addressing a question raised by Pilaud. This also generalizes a recent algorithm for generating lattice congruences of the weak order on the symmetric group. Our algorithms are derived from the Hartung\u2013Hoang\u2013M\u00fctze\u2013Williams combinatorial generation framework, and they yield simple algorithms for computing Hamilton paths and cycles on large classes of polytopes, including chordal nestohedra and quotientopes. In particular, we derive an efficient implementation of the Savage\u2013Squire\u2013West construction. Along the way, we give an overview of old and recent results about the polyhedral and order-theoretic aspects of acyclic orientations of graphs and hypergraphs.<\/jats:p>","DOI":"10.1137\/23m1546567","type":"journal-article","created":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T04:28:11Z","timestamp":1689308891000},"page":"1509-1547","source":"Crossref","is-referenced-by-count":5,"title":["Combinatorial Generation via Permutation Languages. V. Acyclic Orientations"],"prefix":"10.1137","volume":"37","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[{"name":"Computer Science Department, Universit\u00e9 Libre de Bruxelles, Brussels, Belgium."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hung P.","family":"Hoang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1728-6936","authenticated-orcid":true,"given":"Arturo","family":"Merino","sequence":"additional","affiliation":[{"name":"Department of Mathematics, TU Berlin, Berlin, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3143-4955","authenticated-orcid":true,"given":"Ond\u0159ej","family":"Mi\u010dka","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torsten","family":"M\u00fctze","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom & Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,7,14]]},"reference":[{"key":"ref1","author":"Aguiar M.","year":"2017","journal-title":"Mem. Amer. Math. Soc."},{"key":"ref2","first-page":"515","volume":"10","author":"Benedetti C.","year":"2019","journal-title":"J. Comb."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00120-9"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.topol.2005.08.010"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.08.002"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"J. Cardinal , \nA. I. Merino , and \nT. M\u00fctze , Efficient generation of elimination trees and graph associahedra, in Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference\/ Alexandria, VA, \nJ. Naor and \nN. Buchbinder, eds. SIAM, Philadelphia, 2022, pp. 2128\u20132140, https:\/\/doi.org\/10.1137\/1.9781611977073.84.","DOI":"10.1137\/1.9781611977073.84"},{"key":"ref7","unstructured":"The Combinatorial Object Server: Generate acyclic orientations., http:\/\/www.combos.org\/orient."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589496"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.092"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-15124"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90154-1"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"ref13","unstructured":"F. Gray , Pulse Code Communication, 1953, March 17, 1953 (filed Nov. 1947). U.S. Patent 2,632,058."},{"key":"ref14","unstructured":"C. Greene , Acyclic orientations, in Proceedings of the NATO Advanced Study Institute held in Berlin (West Germany), 1976, 1977."},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0712251-1"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/8199"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-021-2186-1"},{"key":"ref18","volume-title":"The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1","author":"Knuth D. E.","year":"2011"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/0607036"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.09.006"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1045"},{"key":"ref22","author":"Meehan E.","year":"2019","journal-title":"The Hopf Algebra of Generic Rectangulations"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00393-w"},{"key":"ref24","first-page":"B73d","volume":"73","author":"Manneville T.","year":"2014","journal-title":"S\u00e9m Lothar. Combin."},{"key":"ref25","author":"M\u00fctze T.","year":"2022","journal-title":"to appear in Electron. J. Combin."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0797-3"},{"key":"ref27","first-page":"67","volume":"86","author":"Pilaud V.","year":"2022","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnn153"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.02.035"},{"key":"ref30","first-page":"11","volume":"85","author":"Padrol A.","year":"2021","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.4171\/dm\/248"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12231"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0405-9_15"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44236-5_10"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44236-5_9"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"S. Rehberg , Combinatorial Reciprocity Theorems for Generalized Permutahedra, Hypergraphs, and Pruned Inside-Out Polytopes, https:\/\/arxiv.org\/abs\/2103.09073, 2021.","DOI":"10.37236\/10371"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.07.005"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"F. Ruskey , Combinatorial Gray code, in Encyclopedia of Algorithms, Springer, New York, 2016, pp. 342\u2013347.","DOI":"10.1007\/978-1-4939-2864-4_732"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144595295272"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2776-6"},{"key":"ref42","unstructured":"C. D. Savage , \nM. B. Squire , and \nD. B. West , Gray code results for acyclic orientations, in Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993), Congr. Numer. 96, Utilitas Math., Winnipeg, MB, Canada, 1993, pp. 185\u2013204."},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1090\/pcms\/013\/08"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1988-0928904-4"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"J. Sawada  and \nA. Williams , A Hamilton path for the Sigma-Tau problem, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2018, pp. 568\u2013575, https:\/\/doi.org\/10.1137\/1.9781611975031.37.","DOI":"10.1137\/1.9781611975031.37"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00201-X"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"A. Williams , Loopless generation of multiset permutations using a constant number of variables by prefix shifts, in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2009, pp. 987\u2013996, https:\/\/doi.org\/10.1137\/1.9781611973068.107.","DOI":"10.1137\/1.9781611973068.107"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_46"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1546567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:31:49Z","timestamp":1787319109000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1546567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,14]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1137\/23M1546567"],"URL":"https:\/\/doi.org\/10.1137\/23m1546567","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,14]]}}}