The traveling salesman problem for cubic graphs.
D. Eppstein.
arXiv:cs.DS/0302030.
8th Worksh. Algorithms and Data
Structures, Ottawa, 2003.
Springer, Lecture Notes in
Comp. Sci. 2748, 2003, pp. 307–318,
doi:10.1007/978-3-540-45078-8_27.
J. Graph Algorithms and Applications 11 (1): 61–81,
2007, doi:10.7155/jgaa.00137.
We find improved exponential-time algorithms for exact solution of the traveling salesman problem on graphs of maximum degree three and four. We also consider related problems including counting the number of Hamiltonian cycles in such graphs.
The case analysis for the cycle-listing algorithm is missing a case, and the algorithms for both finding the minimum-weight Hamiltonian cycle and listing all Hamiltonian cycles in cubic graphs have been improved by others; see my blog post "Cubic salespeople revisited" for details.