A. A. Ageev, A. E. Baburin, E. Kh. Gimadi, “A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight”, Diskretn. Anal. Issled. Oper., Ser. 1, 2006, Volume 13, Issue 2,Pages <nobr>11

This article is cited in 23 papers

A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight

A. A. Ageev, A. E. Baburin, E. Kh. Gimadi

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: We study the problem in which, given a complete undirected edge-weighted graph, it is required to find two (edge) disjoint Hamiltonian cycles of maximum total weight. The problem is known to be NP-hard in the strong sense. We present a 3/4-approximation algorithm with the running time $O(n^3)$.