The problem of finding two disjoint Hamiltonian cycles of minimum sum weight is considered in a complete undirected graph with arbitrarily chosen weights of the edges 1 and 2. The main result of the paper is the presentation of polynomial algorithms with the currently best guaranteed performance factors 26/21 and 6/5. These algorithms are based on finding the partial tours with a large number of edges in the graphs of a special type.
展开▼
