Access Restriction

Author Estivill-Castro, Vladimir ♦ Heednacram, Apichat ♦ Suraweera, Francis
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Covering points with lines ♦ Line cover problem ♦ Parameterized complexity ♦ Practical FPT-algorithm
Abstract We present efficient algorithms to solve the Line Cover Problem exactly. In this NP-complete problem, the inputs are $\textit{n}$ points in the plane and a positive integer $\textit{k},$ and we are asked to answer if we can cover these $\textit{n}$ points with at most $\textit{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 $\textit{k}$ and does not depend on the size $\textit{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 earlier algorithms that use less rules.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-01-05
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 14
Page Count 20
Starting Page 1.7
Ending Page 1.26

Open content in new tab

   Open content in new tab
Source: ACM Digital Library