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

DOI10.1134/S1064562416010233zbMATH Open1339.05309MaRDI QIDQ294361FDOQ294361

Authors: Eh. Kh. Gimadi, I. A. Rykov 

Publication date: 16 June 2016

Published in: Doklady Mathematics (Search for Journal in Brave)

Recommendations

• Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
• On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• On approximating maximum covering cycles in undirected graphs
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
• scientific article; zbMATH DE number 3929052
• Approximation algorithms for maximum weight k-coverings of graphs by packings
• Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
• scientific article; zbMATH DE number 3966112

zbMATH Keywords

\(m\) nonadjacent cycles of maximum total weight

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The traveling salesman problem and its variations
• Minimum-weight cycle covers and their approximability
• Title not available (Why is that?)
• Approximability of the problem about a minimum-weight cycle cover of a graph

Cited In (6)

• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles
• Searching for a cycle with maximum coverage in undirected graphs
• Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
• On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space
• Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces

This page was built for publication: On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294361)