Approximate Mechanisms for the Graphical TSP and Other Graph-Traversal Problems

DOI10.1080/15427951.2008.10129173MaRDI QIDQ3574304zbMATH OpenOpenAlexFDO

Authors D. Bilò, Luca Forlizzi, Luciano Gualà, Guido Proietti

Publication date 9 July 2010

Published in Internet Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/15427951.2008.10129173

Mathematics Subject Classification ID

Internet topics (68M11) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Approximating the regular graphic TSP in near linear time
• Engineering an approximation scheme for traveling salesman in planar graphs
• An approximation algorithm for the TSP
• scientific article; zbMATH DE number 4095236
• Approximation algorithms for graph approximation problems
• On the approximability of the traveling salesman problem (extended abstract)
• On the complexity of approximating TSP with neighborhoods and related problems
• On the complexity of approximating TSP with neighborhoods and related problems

Cited in

(4)

• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• Exact and approximate algorithms for movement problems on (special classes of) graphs
• Approximating TSP Solution by MST Based Graph Pyramid
• An algorithm composition scheme preserving monotonicity

This page was built for publication: Approximate Mechanisms for the Graphical TSP and Other Graph-Traversal Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3574304)