FPT-Algorithms for Minimum-Bends Tours

File Size Format
64445_1.pdf 908Kb Adobe PDF View
Title FPT-Algorithms for Minimum-Bends Tours
Author Estivill-Castro, Vladimir; Heednacram, Apichat; Suraweera, Francis
Journal Name International Journal of Computational Geometry and Applications (IJCGA)
Year Published 2011
Place of publication Singapore
Publisher World Scientific Publishing
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. [note: An earlier version of the Rectilinear κ-Bends Traveling Salesman Problem has been published in COCOON 2010.]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.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1142/S0218195911003615
Copyright Statement Electronic version of an article published in International Journal of Computational Geometry and Applications (IJCGA), Vol. 21(2), 2011, pp. 189-213, http://dx.doi.org/10.1142/S0218195911003615. Copyright World Scientific Publishing Company http://www.worldscinet.com/ijcga/ijcga.shtml
Volume 21
Issue Number 2
Page from 189
Page to 213
ISSN 0218-1959
Date Accessioned 2011-04-15
Date Available 2011-10-20T06:39:30Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Analysis of Algorithms and Complexity
URI http://hdl.handle.net/10072/39781
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice