Computing shortest heterochromatic monotone routes

​
​ ​ ​ ​
Díaz-Báñez, José Miguel
​ ​ ​ ​
Hernández, Gregorio
​ ​ ​ ​
Oliveros, Deborah
​ ​ ​ ​
Ramírez Vigueras, Adriana
orcId Sellarès i Chiva, Joan Antoni​ researcherId Sellarès i Chiva, Joan Antoni​ scopusId Sellarès i Chiva, Joan Antoni​ ​
Sellarès i Chiva, Joan Antoni
​ ​ ​ ​
Urrutia, Jorge
​ ​ ​ ​
Ventura, Inmaculada
Text Complet
AM-ComputingShortest.pdf 187.3  Kb | PDF ​
​
Compartir
​
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 ​
​Tots els drets reservats
Mostra el registre complet de l'element