Cubic salespeople revisited

Good news: Email from Knuth. Bad news: It begins “is there a bug in your paper?” The paper in question is “The traveling salesman problem for cubic graphs” (WADS 2003 and JGAA 2007). Of course the bug report is accurate, but fortunately it can be easily patched. My paper has algorithms for finding a minimum-weight Hamiltonian cycle (when it exists), in an \(n\)-vertex graph of maximum degree three, in time \(O(2^{n/3})\), and for listing all Hamiltonian cycles in time \(O(2^{3n/8})\). Both have since been improved by others. Maciej Liśkiewicz and Martin R. Schuster gave an algorithm for the minimum-weight cycle with time \(O(1.2553^n)\) in their paper “A new upper bound for the traveling salesman problem in cubic graphs” [J. Discrete Algorithms 2014], and Heidi Gebauer gave an algorithm for listing all cycles in time \(O(1.276^n)\) in her paper “Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs” [Elect. J. Combinatorics 2011]. Despite these…