The two-convex-polygons TSP: A solvable case

0.00 Avg rating—0 Votes

Article ID:	iaor2002970
Country:	Spain
Volume:	5
Issue:	1
Start Page Number:	105
End Page Number:	126
Publication Date:	Jan 1997
Journal:	TOP
Authors:	Garca Alfredo, Tejel F. Javier
Keywords:	programming: dynamic

Abstract:

In this paper, the Travelling Salesman Problem when m points are on one convex polygon P, and n points are on another convex polygon Q, inside P, is polynomially solved. For this specific case, an O(m³n³) time and O(m²n²) space algorithm to obtain the tour with minimum length is provided.

Reviews

Required fields are marked *. Your email address will not be published.