×

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)
PDF BibTeX XML Cite