{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:02:00Z","timestamp":1751515320568,"version":"3.41.0"},"reference-count":59,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2153331"],"award-info":[{"award-number":["CCF-2153331"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"National Science Foundation Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1016\/j.dam.2025.06.013","type":"journal-article","created":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T16:29:16Z","timestamp":1751387356000},"page":"208-224","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Circulant TSP: Vertices of the edge-length polytope and superpolynomial lower bounds"],"prefix":"10.1016","volume":"376","author":[{"given":"Samuel C.","family":"Gutekunst","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.dam.2025.06.013_b1","series-title":"The Traveling Salesman Problem: A Computational Study","author":"Applegate","year":"2006"},{"issue":"5","key":"10.1016\/j.dam.2025.06.013_b2","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","article-title":"Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems","volume":"45","author":"Arora","year":"1998","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/j.dam.2025.06.013_b3","first-page":"40","article-title":"On unitary\/strong linear realizations: Buratti\u2013Horak\u2013Rosa conjecture","volume":"29","author":"\u00c1vila","year":"2023","journal-title":"Bol. Soc. Mat. Mexicana"},{"key":"10.1016\/j.dam.2025.06.013_b4","doi-asserted-by":"crossref","DOI":"10.1016\/j.orl.2024.107133","article-title":"Circulant TSP special cases: Easily-solvable cases and improved approximations","volume":"55","author":"Beal","year":"2024","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/j.dam.2025.06.013_b5","doi-asserted-by":"crossref","unstructured":"P. Berman, M. Karpinski, 8\/7-approximation algorithm for (1, 2)-TSP, in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, 2006, pp. 641\u2013648.","DOI":"10.1145\/1109557.1109627"},{"key":"10.1016\/j.dam.2025.06.013_b6","series-title":"Introduction to linear optimization","author":"Bertsimas","year":"1997"},{"issue":"2","key":"10.1016\/j.dam.2025.06.013_b7","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/moor.16.2.259","article-title":"Small travelling salesman polytopes","volume":"16","author":"Boyd","year":"1991","journal-title":"Math. Oper. Res."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jcd.21311","article-title":"Dihedral Hamiltonian cycle systems of the cocktail party graph","volume":"21","author":"Buratti","year":"2013","journal-title":"J. Combin. Des."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b9","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF02614311","article-title":"Efficiently solvable special cases of hard combinatorial optimization problems","volume":"79","author":"Burkard","year":"1997","journal-title":"Math. Program."},{"issue":"3","key":"10.1016\/j.dam.2025.06.013_b10","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1137\/S0036144596297514","article-title":"Well-solvable special cases of the traveling salesman problem: A survey","volume":"40","author":"Burkard","year":"1998","journal-title":"SIAM Rev."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0166-218X(91)90024-Q","article-title":"Efficiently solvable special cases of bottleneck travelling salesman problems","volume":"32","author":"Burkard","year":"1991","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b12","doi-asserted-by":"crossref","first-page":"R44","DOI":"10.37236\/316","article-title":"Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3","volume":"17","author":"Capparelli","year":"2010","journal-title":"Eectron. J. Combinat."},{"key":"10.1016\/j.dam.2025.06.013_b13","first-page":"407","article-title":"The Buratti-Horak-Rosa conjecture holds for some underlying sets of size three","volume":"vol. 462","author":"Chand","year":"2022"},{"issue":"9","key":"10.1016\/j.dam.2025.06.013_b14","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1016\/0167-6377(91)90067-Y","article-title":"A complete description of the traveling salesman polytope on 8 nodes","volume":"10","author":"Christof","year":"1991","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02568602","article-title":"Combinatorial optimization and small polytopes","volume":"4","author":"Christof","year":"1996","journal-title":"Top"},{"key":"10.1016\/j.dam.2025.06.013_b16","series-title":"Worst-case analysis of a new heuristic for the travelling salesman problem","author":"Christofides","year":"1976"},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b17","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580109","article-title":"Edmonds polytopes and weakly Hamiltonian graphs","volume":"5","author":"Chv\u00e1tal","year":"1973","journal-title":"Math. Program."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01582008","article-title":"The traveling salesman problem on a graph and some related integer polyhedra","volume":"33","author":"Cornu\u00e9jols","year":"1985","journal-title":"Math. Program."},{"issue":"3","key":"10.1016\/j.dam.2025.06.013_b19","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/j.disc.2017.11.013","article-title":"A problem on partial sums in abelian groups","volume":"341","author":"Costa","year":"2018","journal-title":"Discrete Math."},{"issue":"16","key":"10.1016\/j.dam.2025.06.013_b20","doi-asserted-by":"crossref","first-page":"1815","DOI":"10.1016\/j.dam.2011.01.026","article-title":"A comparison of lower bounds for the symmetric circulant traveling salesman problem","volume":"159","author":"de Klerk","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2025.06.013_b21","first-page":"42","article-title":"On Hamiltonian paths with prescribed edge lengths in the complete graph","volume":"57","author":"Dinitz","year":"2009","journal-title":"Bull. Inst. Combin. Appl."},{"issue":"5","key":"10.1016\/j.dam.2025.06.013_b22","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1287\/opre.25.5.741","article-title":"Minimizing wallpaper waste, part 1: A class of traveling salesman problems","volume":"25","author":"Garfinkel","year":"1977","journal-title":"Oper. Res."},{"key":"10.1016\/j.dam.2025.06.013_b23","series-title":"Polytopes\u2014Combinatorics and Computation","first-page":"43","article-title":"Polymake: a framework for analyzing convex polytopes","author":"Gawrilow","year":"2000"},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b24","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1017\/S0960129508006609","article-title":"The travelling salesman problem in symmetric circulant matrices with two stripes","volume":"18","author":"Gerace","year":"2008","journal-title":"Math. Structures Comput. Sci."},{"key":"10.1016\/j.dam.2025.06.013_b25","series-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","first-page":"87","article-title":"Well-solved special cases","author":"Gilmore","year":"1985"},{"key":"10.1016\/j.dam.2025.06.013_b26","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.entcs.2006.07.032","article-title":"The traveling salesman problem in circulant weighted graphs with two stripes","volume":"169","author":"Greco","year":"2007","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"2","key":"10.1016\/j.dam.2025.06.013_b27","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1287\/moor.5.2.285","article-title":"On the monotone symmetric travelling salesman problem: hypohamiltonian\/hypotraceable graphs and facets","volume":"5","author":"Gr\u00f6tschel","year":"1980","journal-title":"Math. Oper. Res."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b28","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01582116","article-title":"On the symmetric travelling salesman problem I: inequalities","volume":"16","author":"Gr\u00f6tschel","year":"1979","journal-title":"Math. Program."},{"key":"10.1016\/j.dam.2025.06.013_b29","series-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","first-page":"251","article-title":"Polyhedral theory","author":"Gr\u00f6tschel","year":"1985"},{"issue":"4","key":"10.1016\/j.dam.2025.06.013_b30","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1287\/moor.11.4.537","article-title":"Clique tree inequalities and the symmetric travelling salesman problem","volume":"11","author":"Gr\u00f6tschel","year":"1986","journal-title":"Math. Oper. Res."},{"key":"10.1016\/j.dam.2025.06.013_b31","doi-asserted-by":"crossref","DOI":"10.1007\/s10107-025-02215-2","article-title":"The two-stripe symmetric circulant TSP is in P","author":"Gutekunst","year":"2025","journal-title":"Mathematical Programming"},{"issue":"4","key":"10.1016\/j.dam.2025.06.013_b32","doi-asserted-by":"crossref","first-page":"2452","DOI":"10.1137\/19M1245840","article-title":"Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem","volume":"33","author":"Gutekunst","year":"2019","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b33","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1287\/moor.2022.1265","article-title":"The circlet inequalities: A new, circulant-based, facet-defining inequality for the TSP","volume":"48","author":"Gutekunst","year":"2023","journal-title":"Math. Oper. Res."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b34","doi-asserted-by":"crossref","first-page":"R20","DOI":"10.37236\/109","article-title":"On a problem of Marco Buratti","volume":"16","author":"Horak","year":"2009","journal-title":"Electron. J. Combinat."},{"key":"10.1016\/j.dam.2025.06.013_b35","doi-asserted-by":"crossref","unstructured":"A.R. Karlin, N. Klein, S.O. Gharan, A (slightly) improved approximation algorithm for metric TSP, in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 32\u201345.","DOI":"10.1145\/3406325.3451009"},{"key":"10.1016\/j.dam.2025.06.013_b36","first-page":"8","article-title":"On approximation lower bounds for TSP with bounded metrics","volume":"19","author":"Karpinski","year":"2012","journal-title":"Electron. Colloquium Comput. Complex. (ECCC)"},{"key":"10.1016\/j.dam.2025.06.013_b37","series-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"Lawler","year":"1985"},{"issue":"7","key":"10.1016\/j.dam.2025.06.013_b38","article-title":"Paths through equally spaced points on a circle","volume":"25","author":"McKay","year":"2022","journal-title":"J. Integer Seq."},{"key":"10.1016\/j.dam.2025.06.013_b39","doi-asserted-by":"crossref","unstructured":"E. Medova, Using QAP Bounds for the Circulant TSP to Design Reconfigurable Networks, in: Quadratic Assignment and Related Problems, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, May 20-21, 1993, 1993, pp. 275\u2013292.","DOI":"10.1090\/dimacs\/016\/14"},{"issue":"4","key":"10.1016\/j.dam.2025.06.013_b40","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","article-title":"Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems","volume":"28","author":"Mitchell","year":"1999","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b41","doi-asserted-by":"crossref","first-page":"2:1","DOI":"10.1145\/2739008","article-title":"Removing and adding edges for the traveling salesman problem","volume":"63","author":"M\u00f6mke","year":"2016","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.dam.2025.06.013_b42","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1007\/s00224-012-9439-7","article-title":"139-Approximation for graphic TSP","volume":"55","author":"Mucha","year":"2014","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"10.1016\/j.dam.2025.06.013_b43","doi-asserted-by":"crossref","first-page":"882","DOI":"10.1287\/moor.17.4.882","article-title":"The binested inequalities for the symmetric traveling salesman polytope","volume":"17","author":"Naddef","year":"1992","journal-title":"Math. Oper. Res."},{"key":"10.1016\/j.dam.2025.06.013_b44","series-title":"The Traveling Salesman Problem and Its Variations","first-page":"29","article-title":"Polyhedral theory and branch-and-cut algorithms for the symmetric TSP","author":"Naddef","year":"2007"},{"issue":"1\u20133","key":"10.1016\/j.dam.2025.06.013_b45","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01586945","article-title":"The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities","volume":"51","author":"Naddef","year":"1991","journal-title":"Math. Program."},{"issue":"2","key":"10.1016\/j.dam.2025.06.013_b46","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1287\/moor.17.2.308","article-title":"The crown inequalities for the symmetric traveling salesman polytope","volume":"17","author":"Naddef","year":"1992","journal-title":"Math. Oper. Res."},{"issue":"9","key":"10.1016\/j.dam.2025.06.013_b47","doi-asserted-by":"crossref","DOI":"10.1016\/j.disc.2021.112486","article-title":"New methods to attack the Buratti-Horak-Rosa conjecture","volume":"344","author":"Ollis","year":"2021","journal-title":"Discrete Math."},{"issue":"4","key":"10.1016\/j.dam.2025.06.013_b48","doi-asserted-by":"crossref","DOI":"10.26493\/1855-3974.2659.be1","article-title":"Growable realizations: a powerful approach to the Buratti-Horak-Rosa conjecture","volume":"22","author":"Ollis","year":"2022","journal-title":"Ars Math. Contemp."},{"key":"10.1016\/j.dam.2025.06.013_b49","doi-asserted-by":"crossref","unstructured":"S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem, in: Proceedings of the 52nd Annual IEEE Symposium on the Foundations of Computer Science, 2011, pp. 550\u2013559.","DOI":"10.1109\/FOCS.2011.80"},{"issue":"1","key":"10.1016\/j.dam.2025.06.013_b50","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","article-title":"The traveling salesman problem with distances one and two","volume":"18","author":"Papadimitriou","year":"1993","journal-title":"Math. Oper. Res."},{"key":"10.1016\/j.dam.2025.06.013_b51","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.disc.2013.11.017","article-title":"A new result on the problem of Buratti, Horak and Rosa","volume":"319","author":"Pasotti","year":"2014","journal-title":"Discrete Math."},{"issue":"2","key":"10.1016\/j.dam.2025.06.013_b52","doi-asserted-by":"crossref","DOI":"10.37236\/3879","article-title":"On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs","volume":"21","author":"Pasotti","year":"2014","journal-title":"Electron. J. Combinat."},{"key":"10.1016\/j.dam.2025.06.013_b53","series-title":"Further progress on the Buratti-Horak-Rosa conjecture","author":"Pasotti","year":"2019"},{"issue":"5","key":"10.1016\/j.dam.2025.06.013_b54","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","article-title":"Shorter tours by nicer ears: 7\/5-Approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs","volume":"34","author":"Seb\u0151","year":"2014","journal-title":"Combinatorica"},{"key":"10.1016\/j.dam.2025.06.013_b55","first-page":"76","article-title":"On some extremal walks in graphs","volume":"17","author":"Serdyukov","year":"1978","journal-title":"Upravlyaemye Sistemy"},{"key":"10.1016\/j.dam.2025.06.013_b56","unstructured":"N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, http:\/\/oeis.org."},{"key":"10.1016\/j.dam.2025.06.013_b57","first-page":"53","article-title":"A note on the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs","volume":"94","author":"V\u00e1zquez-Avila","year":"2022","journal-title":"Bull. ICA"},{"key":"10.1016\/j.dam.2025.06.013_b58","series-title":"The Design of Approximation Algorithms","author":"Williamson","year":"2011"},{"key":"10.1016\/j.dam.2025.06.013_b59","series-title":"Integer and Combinatorial Optimization","author":"Wolsey","year":"1999"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X25003282?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X25003282?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T03:33:39Z","timestamp":1751427219000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X25003282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":59,"alternative-id":["S0166218X25003282"],"URL":"https:\/\/doi.org\/10.1016\/j.dam.2025.06.013","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Circulant TSP: Vertices of the edge-length polytope and superpolynomial lower bounds","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.dam.2025.06.013","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}]}}