Geodesic
Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
Applicationes Mathematicae, Tome 22 (1993) no. 3, pp. 351-358.

Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences

The 3-Opt procedure deals with interchanging three edges of a tour with three edges not on that tour. For n≥6, the 3-Interchange Graph is a graph on 1/2(n-1)! vertices, corresponding to the hamiltonian tours in K_n; two vertices are adjacent iff the corresponding hamiltonian tours differ in an interchange of 3 edges; i.e. the tours differ in a single 3-Opt step. It is shown that the 3-Interchange Graph is a hamiltonian subgraph of the Symmetric Traveling Salesman Polytope. Upper bounds are derived for the diameters of the 3-Interchange Graph and the union of the 2- and the 3-Interchange Graphs. Finally, some new adjacency properties for the Asymmetric Traveling Salesman Polytope and the Assignment Polytope are given.
DOI : 10.4064/am-22-3-351-358
Keywords: Assignment Polytope, Traveling Salesman Polytope

Gerard Sierksma 1

1 
@article{10_4064_am_22_3_351_358,
     author = {Gerard Sierksma},
     title = {Hamiltonicity and the {3-Opt} procedure for the traveling {Salesman} problem},
     journal = {Applicationes Mathematicae},
     pages = {351--358},
     publisher = {mathdoc},
     volume = {22},
     number = {3},
     year = {1993},
     doi = {10.4064/am-22-3-351-358},
     zbl = {0818.90126},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/am-22-3-351-358/}
}
TY  - JOUR
AU  - Gerard Sierksma
TI  - Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
JO  - Applicationes Mathematicae
PY  - 1993
SP  - 351
EP  - 358
VL  - 22
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4064/am-22-3-351-358/
DO  - 10.4064/am-22-3-351-358
LA  - en
ID  - 10_4064_am_22_3_351_358
ER  - 
%0 Journal Article
%A Gerard Sierksma
%T Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
%J Applicationes Mathematicae
%D 1993
%P 351-358
%V 22
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4064/am-22-3-351-358/
%R 10.4064/am-22-3-351-358
%G en
%F 10_4064_am_22_3_351_358
Gerard Sierksma. Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem. Applicationes Mathematicae, Tome 22 (1993) no. 3, pp. 351-358. doi : 10.4064/am-22-3-351-358. http://geodesic.mathdoc.fr/articles/10.4064/am-22-3-351-358/

Cité par Sources :