Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles |
| |
Authors: | E Kh Gimadi I A Rykov |
| |
Institution: | 1.Sobolev Institute of Mathematics,Siberian Branch of the Russian Academy of Sciences,Novosibirsk,Russia |
| |
Abstract: | We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O(n 3) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }}{{\ln n}}\), respectively. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|