Geodesic
The Traveling Salesman Problem for Cubic Graphs
Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 61-81.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We show how to find a Hamiltonian cycle in a graph of degree at most three with n vertices, in time O(2n/3) ≈ 1.260n 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(23n/8) ≈ 1.297n. 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.890n and O((27/4+ε)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(23n/8) Hamiltonian cycles; we also exhibit a family of graphs with 2n/3 Hamiltonian cycles per graph. 
@article{JGAA_2007_11_1_a2,
     author = {David Eppstein},
     title = {The {Traveling} {Salesman} {Problem} for {Cubic} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {61--81},
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2007},
     doi = {10.7155/jgaa.00137},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00137/}
}
TY  - JOUR
AU  - David Eppstein
TI  - The Traveling Salesman Problem for Cubic Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2007
SP  - 61
EP  - 81
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00137/
DO  - 10.7155/jgaa.00137
LA  - en
ID  - JGAA_2007_11_1_a2
ER  - 
%0 Journal Article
%A David Eppstein
%T The Traveling Salesman Problem for Cubic Graphs
%J Journal of Graph Algorithms and Applications
%D 2007
%P 61-81
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00137/
%R 10.7155/jgaa.00137
%G en
%F JGAA_2007_11_1_a2
David Eppstein. The Traveling Salesman Problem for Cubic Graphs. Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 61-81. doi : 10.7155/jgaa.00137. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00137/

Cité par Sources :