Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio

DOI10.1016/j.endm.2009.02.004zbMath1267.90162OpenAlexW1613650767MaRDI QIDQ2839206

Vladimir G. Deǐneko, Alexander Tiskin

Publication date: 4 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.02.004

zbMATH Keywords

approximation algorithmsmetric TSPdouble-tree shortcutting

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Approximating the metric TSP in linear time

Cites Work

• The Euclidean traveling salesman problem is NP-complete
• Good triangulations yield good tours
• The Travelling Salesman and the PQ-Tree
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On two geometric problems related to the travelling salesman problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Tight bounds for christofides' traveling salesman heuristic
• Approximating the Metric TSP in Linear Time
• Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio