Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

DOI10.1134/S0081543816090078MaRDI QIDQ2396372zbMATH OpenOpenAlexFDO

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

Publication date 8 June 2017

Published in Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation accuracyapproximation algorithmsasymptotic optimalitycomputational complexitycycle cover of a graphprobabilistic analysisrandom instancestraveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
• On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space
• Constant-factor approximations for cycle cover problems
• Improved approximation algorithms for some min-max and minimum cycle cover problems
• New approximation algorithms for the minimum cycle cover problem

Cites work

• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Approximability of the problem about a minimum-weight cycle cover of a graph
• scientific article; zbMATH DE number 4068645 (Why is no real title available?)
• On Random Symmetric Travelling Salesman Problems
• On the value of a random minimum spanning tree problem

Cited in

(7)

• On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space
• On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
• Searching for a cycle with maximum coverage in undirected graphs
• scientific article; zbMATH DE number 892042 (Why is no real title available?)
• 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
• Constant-ratio polynomial time approximation of the asymmetric minimum weight cycle cover problem with limited number of cycles

This page was built for publication: Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

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