FPT-algorithms for minimum-bends tours
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Estivill-Castro, V. (Vladimir)
- dc.contributor.author Heednacram, Apichat
- dc.contributor.author Suraweera, Francis
- dc.date.accessioned 2020-03-12T16:44:23Z
- dc.date.available 2020-03-12T16:44:23Z
- dc.date.issued 2011
- dc.description.abstract This paper discusses the κ-BENDS TRAVELING SALESMAN PROBLEM. In this NP-complete problem, the inputs are n points in the plane and a positive integer κ, and we are asked whether we can travel in straight lines through these n points with at most κ bends. There are a number of applications where minimizing the number of bends in the tour is desirable because bends are considered very costly. We prove that this problem is fixed-parameter tractable (FPT). The proof is based on the kernelization approach. We also consider the RECTILINEAR κ-BENDS TRAVELING SALESMAN PROBLEM, which requires that the line-segments be axis-parallel.1 Note that a rectilinear tour with κ bends is a cover with κ-line segments, and therefore a cover by lines. We introduce two types of constraints derived from the distinction between line-segments and lines. We derive FPT-algorithms with different techniques and improved time complexity for these cases.en
- dc.format.mimetype application/pdf
- dc.identifier.citation Estivill-Castro V, Heednacram A, Suraweera F. FPT-algorithms for minimum-bends tours. Int J Comput Geom Appl. 2011 Apr;21(2):189-213. DOI: 10.1142/S0218195911003615
- dc.identifier.doi http://dx.doi.org/10.1142/S0218195911003615
- dc.identifier.issn 0218-1959
- dc.identifier.uri http://hdl.handle.net/10230/43890
- dc.language.iso eng
- dc.publisher World Scientific Publishing
- dc.relation.ispartof International Journal of Computational Geometry and Applications. 2011 Apr;21(2):189-213
- dc.rights Electronic version of an article published as International Journal of Computational Geometry and Applications 2011 Apr;21(2):189-213. DOI: 10.1142/S0218195911003615 © copyright World Scientific Publishing Company https://www.worldscientific.com/worldscinet/ijcga
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.subject.keyword Computational geometryen
- dc.subject.keyword Fixed-parameter tractableen
- dc.subject.keyword Minimum-bends toursen
- dc.subject.keyword Covering with hyperplanesen
- dc.title FPT-algorithms for minimum-bends tours
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/acceptedVersion