The two-convex-polygons TSP: A solvable case |
| |
| Authors: | Alfredo García F Javier Tejel |
| |
| Institution: | (1) Dept. de Métodos Estadísticos Facultad de Ciencias, Universidad de Zaragoza, Spain |
| |
| Abstract: | In this paper, the Travelling Salesman Problem whenm points are on one convex polygonP, andn points are on another convex polygonQ, insideP, is polynomially solved. For this specific case, anO(m
3
n
3) time andO(m
2
n
2) space algorithm to obtain the tour with minimum length is provided. |
| |
| Keywords: | Travelling salesman problem convex polygon dynamic programming |
| 本文献已被 SpringerLink 等数据库收录！ |
