DUGiDocsComputing shortest heterochromatic monotone routes
dc.contributor.author
dc.date.accessioned
2018-11-20T15:05:19Z
dc.date.available
2018-11-20T15:05:19Z
dc.date.issued
2008-11-01
dc.identifier.issn
0167-6377
dc.identifier.uri
dc.description.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
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier
dc.relation.isformatof
Versió postprint del document publicat a: https://doi.org/10.1016/j.orl.2008.06.008
dc.relation.ispartof
© Operations Research Letters, 2008, vol. 36, núm. 6, p. 684-687
dc.relation.ispartofseries
Articles publicats (D-IMA)
dc.rights
Tots els drets reservats
dc.subject
dc.title
Computing shortest heterochromatic monotone routes
dc.type
info:eu-repo/semantics/article
dc.rights.accessRights
info:eu-repo/semantics/openAccess
dc.type.version
info:eu-repo/semantics/acceptedVersion
dc.identifier.doi
dc.identifier.idgrec
010258
dc.type.peerreviewed
peer-reviewed