On the Asymptotic Optimality of a Solution of the Euclidean
Problem of Covering a Graph by m Nonadjacent Cycles
of Maximum Total Weight

E. Kh. Gimadi and I. A. Rykov

Presented by Academician Yu.L. Ershov July 20, 2015

Received July 31, 2015

Abstract—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 ^d by m nonadjacent cycles of maximum total weight. The algorithm
has time complexity (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.

DOI: 10.1134/S1064562416010233

Pleiades Publishing home page | journal home page | top

If you have any problems with this server, contact webmaster.