Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143478 | Operations Research Letters | 2008 | 4 Pages |
Abstract
Given a set of n points on the plane colored with kâ¤n colors, the Trip Planning Problem asks for the shortest path visiting the k colors. It is a well-known NP-hard problem. We show that under some natural constraints on the path, the problem can be solved in polynomial time.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
J.M. DÃaz-Báñez, G. Hernández, D. Oliveros, A. RamÃrez-Vigueras, J.A. Sellarès, J. Urrutia, I. Ventura,