Improved Analysis of an Exact Algorithm for Cubic Graph TSP

Maciej Liskiewicz, Martin R. Schuster


We provide a new upper bound for traveling salesman problem (TSP) in cubic graphs, i.e. graphs with maximum vertex degree three, and prove that the problem for an n-vertex graph can be solved in O(1.2553n) time and in linear space. We show that the exact TSP algorithm of Eppstein, with some minor modifications, yields the stated result. The previous best known upper bound O(1.251n) was claimed by Iwama and Nakashima [Proc. COCOON 2007]. Unfortunately, their analysis contains several mistakes that render the proof for the upper bound invalid.
Original languageEnglish
Publication statusPublished - 2012


Dive into the research topics of 'Improved Analysis of an Exact Algorithm for Cubic Graph TSP'. Together they form a unique fingerprint.

Cite this