The Traveling Salesman Problem in Circulant Weighted Graphs With Two Stripes | Zendy

Federico Greco | Zendy; Ivan Gerace | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Traveling Salesman Problem in Circulant Weighted Graphs With Two Stripes

Author(s) -

Federico Greco,

Ivan Gerace

Publication year - 2007

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2006.07.032

Subject(s) - hamiltonian path , circulant matrix , travelling salesman problem , upper and lower bounds , mathematics , combinatorics , hamiltonian (control theory) , constructive , circulant graph , discrete mathematics , hamiltonian path problem , bottleneck traveling salesman problem , graph theory , graph , mathematical optimization , computer science , line graph , mathematical analysis , process (computing) , operating system , voltage graph

The Symmetric Circulant Traveling Salesman Problem asks for the minimum cost of a Hamiltonian cycle in a circulant weighted undirected graph. The computational complexity of this problem is not known. Just a constructive upper bound, and a good lower bound have been determined.This paper provides a characterization of the two stripe case. Instances where the minimum cost of a Hamiltonian cycle is equal either to the upper bound, or to the lower bound are recognized. A new construction providing Hamiltonian cycles, whose cost is in many cases lower than the upper bound, is proposed for the remaining instances

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research