On the asymptotic optimality of a solution of the euclidean problem of covering a graph by m nonadjacent cycles of maximum total weight

Resumo

In the problem of covering an n-vertex graph by m cycles of maximum total weight, it is required to find a family of m vertex-nonadjacent cycles such that it covers all vertices of the graph and the total weight of edges in the cover is maximum. The paper presents an algorithm for approximately solving the problem of covering a graph in Euclidean d-space R^d by m nonadjacent cycles of maximum total weight. The algorithm has time complexity O(n³). An estimate of the accuracy of the algorithm depending on the parameters d, m, and n is substantiated; it is shown that if the dimension d of the space is fixed and the number of covering cycles is m = o(n), then the algorithm is asymptotically exact.