Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

详细

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³) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }}
{{\ln n}}\), respectively.