Name
Abstract | ||
|---|---|---|
We present a polynomial-time algorithm for a variant of the Euclidean traveling salesman tour where n vertices are on the boundary of a convex polygon P and m vertices form the boundary of a convex polygonal obstacle Q completely contained within P. In the worst case the algorithm needs O(m2 lg m + m2n) time and O(nm + m2) space. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.ipl.2005.04.002 | Inf. Process. Lett. |
Keywords | Field | DocType |
computational geometry,network flow,euclidean tsp,convex analysis,nested convex obstacle,traveling salesman problem,traveling salesman | Flow network,Discrete mathematics,Combinatorics,Information processing,Computational geometry,Regular polygon,Travelling salesman problem,Euclidean geometry,Convex analysis,Mathematics | Journal |
Volume | Issue | ISSN |
95 | 2 | 0020-0190 |
Citations | PageRank | References |
3 | 0.52 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeff Abrahamson | 1 | 48 | 6.07 |
| A. Shokoufandeh | 2 | 1356 | 88.63 |
| Pawel Winter | 3 | 99 | 12.98 |