The Travelling Salesman Problem in symmetric circulant matrices with two stripes

DOI10.1017/S0960129508006609zbMATH Open1172.90476MaRDI QIDQ5458063FDOQ5458063

Authors: Ivan Gerace, Federico Greco 

Publication date: 10 April 2008

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Recommendations

• The traveling salesman problem in circulant weighted graphs with two stripes
• The two-stripe symmetric circulant TSP is in P
• A comparison of lower bounds for the symmetric circulant traveling salesman problem
• Hamiltonian cycles in circulant digraphs with two stripes
• Efficiently solvable special cases of bottleneck travelling salesman problems

zbMATH Keywords

upper bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• A solution of the isomorphism problem for circulant graphs
• On hamiltonian Toeplitz graphs
• Efficiently solvable special cases of bottleneck travelling salesman problems
• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• Hamiltonian cycles in circulant digraphs with two stripes

Cited In (7)

• A comparison of lower bounds for the symmetric circulant traveling salesman problem
• Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• The travelling salesman problem on permuted Monge matrices
• Development of an algorithm for solving an asymmetric routing problem based on the ant colony method
• The two-stripe symmetric circulant TSP is in P
• The maximum travelling salesman problem on symmetric Demidenko matrices

This page was built for publication: The Travelling Salesman Problem in symmetric circulant matrices with two stripes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458063)