The two-stripe symmetric circulant TSP is in P

DOI10.1007/978-3-031-06901-7_24zbMath1497.90174arXiv2207.10254OpenAlexW4285235931MaRDI QIDQ2164712

Billy Jin, Samuel C. Gutekunst, David P. Williamson

Publication date: 16 August 2022

Full work available at URL: https://arxiv.org/abs/2207.10254

zbMATH Keywords

Hamiltonian pathpolynomial-timetwo-stripe symmetric circulant

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• Efficiently solvable special cases of bottleneck travelling salesman problems
• Efficiently solvable special cases of hard combinatorial optimization problems
• Hamiltonian cycles in circulant digraphs with two stripes
• The Design of Approximation Algorithms
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
• The Travelling Salesman Problem in symmetric circulant matrices with two stripes

This page was built for publication: The two-stripe symmetric circulant TSP is in P