# zbMATH — the first resource for mathematics

A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight. (Russian) Zbl 1249.05232
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)$$.

##### MSC:
 05C45 Eulerian and Hamiltonian graphs 05C85 Graph algorithms (graph-theoretic aspects)
##### Keywords:
Hamiltonian cycle; polynomial approximation