The traveling salesman problem for cubic graphs
| dc.creator | Eppstein, David | |
| dc.date | 2003-02-20 | |
| dc.date | 2004-04-19 | |
| dc.date.accessioned | 2026-07-07T08:09:28Z | |
| dc.date.available | 2026-07-07T08:09:28Z | |
| dc.description | We show how to find a Hamiltonian cycle in a graph of degree at most three with n vertices, in time O(2^{n/3}) ~= 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 O(2^{3n/8}) ~= 1.297^n. We also solve the traveling salesman problem in graphs of degree at most four, by randomized and deterministic algorithms with runtime 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 O(2^{3n/8}) Hamiltonian cycles; we also exhibit a family of graphs with 2^{n/3} Hamiltonian cycles per graph. | |
| dc.description | 20 pages, 8 figures. A preliminary version of this paper appeared at the 8th Worksh. Algorithms and Data Structures, LNCS 2748, Springer-Verlag, 2003, pp. 307-318. This version generalizes an algorithm from the previous version, to generate all cycles instead of counting them. It also includes a derandomized version of the degree-four algorithm and an implementation of the cycle listing algorithm | |
| dc.identifier | https://arxiv.org/abs/cs/0302030 | |
| dc.identifier | http://arxiv.org/abs/cs/0302030 | |
| dc.identifier | J. Graph Algorithms and Applications 11(1):61-81, 2007 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/131551 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.2 | |
| dc.title | The traveling salesman problem for cubic graphs | |
| dc.type | text |