{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:29Z","timestamp":1750307729207,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            We present efficient algorithms to solve the Line Cover Problem exactly. In this NP-complete problem, the inputs are\n            <jats:italic>n<\/jats:italic>\n            points in the plane and a positive integer\n            <jats:italic>k<\/jats:italic>\n            , and we are asked to answer if we can cover these\n            <jats:italic>n<\/jats:italic>\n            points with at most\n            <jats:italic>k<\/jats:italic>\n            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\n            <jats:italic>k<\/jats:italic>\n            and does not depend on the size\n            <jats:italic>n<\/jats:italic>\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.\n          <\/jats:p>","DOI":"10.1145\/1498698.1626535","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":1,"title":["Reduction rules deliver efficient FPT-algorithms for covering points with lines"],"prefix":"10.1145","volume":"14","author":[{"given":"Vladimir","family":"Estivill-Castro","sequence":"first","affiliation":[{"name":"Griffith University, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Apichat","family":"Heednacram","sequence":"additional","affiliation":[{"name":"Griffith University, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francis","family":"Suraweera","sequence":"additional","affiliation":[{"name":"Griffith University, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187809"},{"key":"e_1_2_1_2_1","unstructured":"Applegate D. Bixby R. Chv\u00e1tal V. and Cook W. 2006. The Traveling Salesman Problem. Princeton University Press Princeton NJ.   Applegate D. Bixby R. Chv\u00e1tal V. and Cook W. 2006. The Traveling Salesman Problem. Princeton University Press Princeton NJ."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434267"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00015-8"},{"key":"e_1_2_1_5_1","unstructured":"CGAL\n\n  \n   Editorial Board. 2007. CGAL User and Reference Manual 3.3 edition. http:\/\/www.cgal.org\/Manual\/3.3\/doc_html\/cgal_manual\/packages.html.  CGAL Editorial Board. 2007. CGAL User and Reference Manual 3.3 edition. http:\/\/www.cgal.org\/Manual\/3.3\/doc_html\/cgal_manual\/packages.html."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00125-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Downey R. and Fellows M. 1999. Parameterized Complexity. Springer New York.  Downey R. and Fellows M. 1999. Parameterized Complexity. Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"volume-title":"Proceedings of the 17th Canadian Conference on Computational Geometry","author":"Drysdale R.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222031"},{"key":"e_1_2_1_11_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer Berlin.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer Berlin."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm053"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11758471_4"},{"volume-title":"Proceedings of the 3rd Canadian Conference on Computational Geometry","author":"Guibas L.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00020-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm040"},{"volume-title":"Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP'00)","author":"Kumar V.","key":"e_1_2_1_17_1"},{"volume-title":"Proceedings of the 11th Fall Workshop on Computational Geometry","author":"Langerman S.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the 10th European Symposium on Algorithms. Springer","author":"Langerman S.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1108-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.286304"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)80467-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98528"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90039-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Niedermeier R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications 31. Oxford University Press New York.  Niedermeier R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications 31. Oxford University Press New York.","DOI":"10.1093\/acprof:oso\/9780198566076.003.0004"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220106"},{"volume-title":"Proceedings of the 8th International IPCO Conference. Springer","author":"Stein C.","key":"e_1_2_1_27_1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1626535","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1626535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:38Z","timestamp":1750253918000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1626535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":27,"alternative-id":["10.1145\/1498698.1626535"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1626535","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}