Fast minimum-weight double-tree shortcutting for metric TSP

DOI10.1145/1498698.1594232zbMath1284.90063MaRDI 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 algorithms; double-tree shortcutting; Metric TSP

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

90C27: Combinatorial optimization

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Approximating the metric TSP in linear time