×

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
PDF BibTeX XML Cite
Full Text: DOI EMIS EuDML