The Rectilinear κ-Bends TSP

File Size Format
63389_1.pdf 410Kb Adobe PDF View
Title The Rectilinear κ-Bends TSP
Author Estivill-Castro, Vladimir; Heednacram, Apichat; Suraweera, Francis
Journal Name Lecture Notes in Computer Science
Year Published 2010
Place of publication Germany
Publisher Springer
Abstract We study a hard geometric problem. Given n points in the plane and a positive integer k, the Rectilinear k -Bends Traveling Salesman Problem asks if there is a piecewise linear tour through the n points with at most k bends where every line-segment in the path is either horizontal or vertical. The problem has applications in VLSI design. We prove that this problem belongs to the class FPT (fixed-parameter tractable). We give an algorithm that runs in O(kn 2 + k 4k n) time by kernelization. We present two variations on the main result. These variations are derived from the distinction between line-segments and lines. Note that a rectilinear tour with k bends is a cover with k line-segments, and therefore a cover by lines. We derive FPT-algorithms using bounded-search-tree techniques and improve the time complexity for these variants.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1007/978-3-642-14031-0_30
Copyright Statement Copyright 2010 Springer Berlin / Heidelberg. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. The original publication is available at www.springerlink.com
Volume 6196
Page from 264
Page to 277
ISSN 0302-9743
Date Accessioned 2010-08-14
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/34462
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice