Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00137
The Traveling Salesman Problem for Cubic Graphs
Vol. 11, no. 1, pp. 6181, 2007. Regular paper.
Abstract We show how to find a Hamiltonian cycle in a graph of degree at most three with n vertices, in time
O(2^{n/3}) ≈ 1.260^{n} and linear space. Our algorithm can find the minimum weight Hamiltonian cycle (traveling salesman problem), in the same time bound.
We can also count or list all Hamiltonian cycles in a degree three graph
in time O(2^{3n/8}) ≈ 1.297^{n}.
We also solve the traveling salesman problem in graphs of degree at most four, by randomized and deterministic algorithms with runtime O((27/4)^{n/3}) ≈ 1.890^{n} and O((27/4+ϵ)^{n/3}) respectively. Our algorithms allow the input to specify a set of forced edges which must be part of any generated cycle.
Our cycle listing algorithm shows that every degree three graph has O(2^{3n/8}) Hamiltonian cycles; we also exhibit a family of graphs with 2^{n/3} Hamiltonian cycles per graph.

Journal Supporters
