{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:01Z","timestamp":1761621061629},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2011,4]]},"abstract":"<jats:p> This paper discusses the \u03ba-BENDS TRAVELING SALESMAN PROBLEM. In this NP-complete problem, the inputs are n points in the plane and a positive integer \u03ba, and we are asked whether we can travel in straight lines through these n points with at most \u03ba 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 \u03ba-BENDS TRAVELING SALESMAN PROBLEM, which requires that the line-segments be axis-parallel. <jats:sup>1<\/jats:sup> Note that a rectilinear tour with \u03ba bends is a cover with \u03ba-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. <\/jats:p>","DOI":"10.1142\/s0218195911003615","type":"journal-article","created":{"date-parts":[[2011,4,11]],"date-time":"2011-04-11T20:43:10Z","timestamp":1302554590000},"page":"189-213","source":"Crossref","is-referenced-by-count":5,"title":["FPT-ALGORITHMS FOR MINIMUM-BENDS TOURS"],"prefix":"10.1142","volume":"21","author":[{"given":"VLADIMIR","family":"ESTIVILL-CASTRO","sequence":"first","affiliation":[{"name":"School of Information and Communication Technology, Griffith University, Nathan, QLD, 4111, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"APICHAT","family":"HEEDNACRAM","sequence":"additional","affiliation":[{"name":"Institute for Integrated and Intelligent Systems, Griffith University, Nathan, QLD, 4111, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FRANCIS","family":"SURAWEERA","sequence":"additional","affiliation":[{"name":"School of Information and Communication Technology, Griffith University, Nathan, QLD, 4111, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","volume-title":"The Traveling Salesman Problem","author":"Applegate D.","year":"2006"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)80467-7"},{"key":"rf6","first-page":"423","volume":"61","author":"Klamkin M.","journal-title":"Amer. Math. Monthly"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.2307\/2308156"},{"key":"rf8","first-page":"443","volume":"62","author":"Selfridge J.","journal-title":"Amer. Math. Monthly"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00502-1"},{"key":"rf10","first-page":"622","volume":"16","author":"Estivill-Castro V.","journal-title":"J. Universal Comput. Sci."},{"key":"rf11","volume":"2","author":"de Berg M.","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434267"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9127-1"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590400138X"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"rf19","series-title":"Texts in Theoretical Computer Science","volume-title":"Parameterized Complexity Theory","author":"Flum J.","year":"2006"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90039-6"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1108-4"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00020-8"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195911003615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:24:04Z","timestamp":1565123044000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195911003615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":18,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1142\/S0218195911003615"],"URL":"https:\/\/doi.org\/10.1142\/s0218195911003615","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4]]}}}