A 3/4-approximation algorithm for finding two disjoint Hamiltonian cycles of maximum weight |
| |
| Authors: | A A Ageev A E Baburin E Kh Gimadi |
| |
| Institution: | (1) Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia |
| |
| 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). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
