Ageev, A. A.; Baburin, A. E.; Gimadi, Eh. Kh. A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight. (Russian) Zbl 1249.05232 Diskretn. Anal. Issled. Oper., Ser. 1 13, No. 2, 11-20 (2006). Summary: 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)\). Cited in 3 Documents MSC: 05C45 Eulerian and Hamiltonian graphs 05C85 Graph algorithms (graph-theoretic aspects) Keywords:Hamiltonian cycle; polynomial approximation PDF BibTeX XML Cite \textit{A. A. Ageev} et al., Diskretn. Anal. Issled. Oper., Ser. 1 13, No. 2, 11--20 (2006; Zbl 1249.05232)