Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
Edward Kh. Gimadi, Ivan A. Rykov · Proceedings of the Steklov Institute of Mathematics · 2016
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.