Computing shortest heterochromatic monotone routes

0.00 Avg rating—0 Votes

Article ID:	iaor20102901
Volume:	36
Issue:	6
Start Page Number:	684
End Page Number:	687
Publication Date:	Nov 2008
Journal:	Operations Research Letters
Authors:	Joret Gwenal, Hernndez G, Oliveros D, Ramrez-Vigueras A, Sellars J A, Urrutia J, Ventura I

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.

Reviews

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