Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
Edward Kh. Gimadi · Proceedings of the Steklov Institute of Mathematics · 2008
The paper presents a polynomial approximation algorithm A solving the problem of finding one and two edge-disjoint Hamiltonian cycles (traveling salesman routes) of maximal weight in a complete weighted undirected graph in multidimensional Euclidean space. The asymptotic optimality of the algorithm is established.