Computer Science – Data Structures and Algorithms
Scientific paper
2003-02-20
J. Graph Algorithms and Applications 11(1):61-81, 2007
Computer Science
Data Structures and Algorithms
20 pages, 8 figures. A preliminary version of this paper appeared at the 8th Worksh. Algorithms and Data Structures, LNCS 2748
Scientific paper
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.
No associations
LandOfFree
The traveling salesman problem for cubic graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The traveling salesman problem for cubic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The traveling salesman problem for cubic graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-723868