# zbMATH — the first resource for mathematics

The traveling salesman problem for cubic graphs. (English) Zbl 1161.68662
Summary: We show how to find a Hamiltonian cycle in a graph of degree at most three with $$n$$ vertices, in time $$\mathcal O(2^{n/3}) \approx 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 $$\mathcal O(2^{3 n/8}) \approx 1.297^n$$. We also solve the traveling salesman problem in graphs of degree at most four, by randomized and deterministic algorithms with runtime $$\mathcal O((27/4)^{n/3})$$ $$1.890^n$$ and $$O((27/4 + \epsilon)^{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 $$\mathcal O(2^{3n/8})$$ Hamiltonian cycles; we also exhibit a family of graphs with $$2^{n/3}$$ Hamiltonian cycles per graph.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 68W05 Nonnumerical algorithms 90C35 Programming involving graphs or networks
##### Keywords:
minimum weight Hamiltonian cycle
Full Text: