Fast minimum-weight double-tree shortcutting for metric TSP

DOI10.1145/1498698.1594232zbMath1284.90063OpenAlexW1998414344MaRDI QIDQ5406222

Vladimir G. Deǐneko, Alexander Tiskin

Publication date: 1 April 2014

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1498698.1594232

zbMATH Keywords

approximation algorithmsdouble-tree shortcuttingMetric TSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Approximating the metric TSP in linear time

This page was built for publication: Fast minimum-weight double-tree shortcutting for metric TSP