Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
From MaRDI portal
Publication:735647
DOI10.1134/S0081543808060072zbMath1178.90335OpenAlexW1979745090MaRDI QIDQ735647
Publication date: 23 October 2009
Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s0081543808060072
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (7)
Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ Approximability of the minimum-weight \(k\)-size cycle cover problem ⋮ A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ 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 ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
Cites Work
This page was built for publication: Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
