Approximability of the problem about a minimum-weight cycle cover of a graph

DOI10.1134/S1064562415020313zbMath1351.05127OpenAlexW766530756MaRDI QIDQ492748

Katherine Neznakhina, Mikhail Yu. Khachay

Publication date: 21 August 2015

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

Full work available at URL: https://doi.org/10.1134/s1064562415020313

Mathematics Subject Classification ID

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

Related Items

Optimal routing in problemsof sequential traversal of megapolises in the presence of constraints ⋮ On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight ⋮ Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem ⋮ An exact algorithm with linear complexity for a problem of visiting megalopolises ⋮ Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles ⋮ A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension ⋮ Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• The Euclidean traveling salesman problem is NP-complete
• Quad trees: A data structure for retrieval by composite keys
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• P-Complete Approximation Problems