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

DOI10.1134/S0081543816090078zbMath1375.90255OpenAlexW2582648747MaRDI QIDQ2396372

E. 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

computational complexityprobabilistic analysistraveling salesman problemapproximation algorithmsasymptotic optimalityrandom instancesapproximation accuracycycle cover of a graph

Mathematics Subject Classification ID

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

Related Items (1)

Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles

Cites Work

• Unnamed Item
• 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
• On the value of a random minimum spanning tree problem
• On Random Symmetric Travelling Salesman Problems

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