Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem

Volume 22 / 1994

Gerard Sierksma Applicationes Mathematicae 22 (1994), 351-358 DOI: 10.4064/am-22-3-351-358


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.


  • Gerard Sierksma

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image