- Tytuł:
- Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
- Autorzy:
- Sierksma, Gerard
- Powiązania:
- https://bibliotekanauki.pl/articles/1340570.pdf
- Data publikacji:
- 1994
- Wydawca:
- Polska Akademia Nauk. Instytut Matematyczny PAN
- Tematy:
-
Assignment Polytope
Traveling Salesman Polytope - Opis:
- 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.
- Źródło:
-
Applicationes Mathematicae; 1993-1995, 22, 3; 351-358
1233-7234 - Pojawia się w:
- Applicationes Mathematicae
- Dostawca treści:
- Biblioteka Nauki
Artykuł