Show simple item record Estivill-Castro, V. (Vladimir) Heednacram, Apichat Suraweera, Francis 2020-03-12T16:44:23Z 2020-03-12T16:44:23Z 2011
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.issn 0218-1959
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.
dc.format.mimetype application/pdf
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
dc.title FPT-algorithms for minimum-bends tours
dc.type info:eu-repo/semantics/article
dc.subject.keyword Computational geometry
dc.subject.keyword Fixed-parameter tractable
dc.subject.keyword Minimum-bends tours
dc.subject.keyword Covering with hyperplanes
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/acceptedVersion


This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account


In collaboration with Compliant to Partaking