Euclidean TSP on two polygons

DOI10.1016/J.TCS.2009.12.003MaRDI QIDQ2268868zbMATH OpenOpenAlexFDO

Authors Jeff Abrahamson, Ali Shokoufandeh

Publication date 9 March 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.12.003

zbMATH Keywords

computational geometryconvex analysisnetwork flowtraveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• The two-convex-polygons TSP: A solvable case
• Approximation algorithms for TSP with neighborhoods in the plane
• The traveling salesman problem with few inner points
• The geometric maximum traveling salesman problem
• scientific article; zbMATH DE number 1163704

Cites work

• A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems
• Efficient special case algorithms for the n-line planar traveling salesman problem
• Euclidean TSP between two nested convex obstacles
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 3479762 (Why is no real title available?)
• scientific article; zbMATH DE number 3571852 (Why is no real title available?)
• scientific article; zbMATH DE number 3371832 (Why is no real title available?)
• The convex-hull-and-line traveling salesman problem: A solvable case
• The n-line traveling salesman problem
• The travelling salesman problem on permuted Monge matrices

Cited in

(9)

• The two-convex-polygons TSP: A solvable case
• Lexicographically minimizing axial motions for the Euclidean TSP
• Touring disjoint polygons problem is NP-hard
• Euclidean TSP with few inner points in linear space
• The geometric maximum traveling salesman problem
• Non-Euclidean Traveling Salesman Problem
• Euclidean TSP in narrow strips
• Euclidean TSP in narrow strips
• TSP in a simple polygon

This page was built for publication: Euclidean TSP on two polygons

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