Reduction Rules Deliver Efficient FPT Algorithms for Covering Points with Lines

File Size Format
61052_1.pdf 466Kb Adobe PDF View
Title Reduction Rules Deliver Efficient FPT Algorithms for Covering Points with Lines
Author Estivill-Castro, Vladimir; Heednacram, Apichat; Suraweera, Francis
Journal Name Journal of Experimental Algorithmics
Year Published 2009
Place of publication USA
Publisher Association for Computing Machinery
Abstract We present efficient algorithms to solve the LINE COVER problem exactly. In this NP-complete problem, the inputs are n points in the plane and a positive integer k, and we are asked to answer if we can cover these n points with at most k lines. Our approach is based on fixed-parameter tractability, and in particular, kernelization. We propose several reduction rules to transform instances of LINE COVER into equivalent smaller instances. Once instances are no longer susceptible to these reduction rules, we obtain a problem kernel whose size is bounded by a polynomial function of the parameter k and does not depend on the size n of the input. Our algorithms provide exact solutions and are easy to implement. We also describe the design of algorithms to solve the corresponding optimization problem exactly. We experimentally evaluated ten variants of the algorithms to determine the impact and trade-offs of several reduction rules. We show that our approach provides tractability for a larger range of values of the parameter and larger inputs, improving the execution time by several orders of magnitude with respect to previously known algorithms.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.jea.acm.org/
Alternative URI http://doi.acm.org/10.1145/1498698.1626535
Copyright Statement Copyright ACM, 2009. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Journal of Experimental Algorithmics (JEA), Volume 14, December 2009, http://doi.acm.org/10.1145/1498698.1626535
Volume 14
Page from 1
Page to 26
ISSN 1084-6654
Date Accessioned 2010-03-04
Date Available 2010-05-17T06:25:37Z
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/29702
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice