A kernelization algorithm for d-Hitting Set

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.date.accessioned 2015-12-07T09:32:11Z
dc.date.available 2015-12-07T09:32:11Z
dc.date.copyright 2010
dc.date.issued 2015-12-07
dc.identifier.issn 0022-0000 en_US
dc.identifier.uri http://hdl.handle.net/10725/2772
dc.description.abstract For a given parameterized problem, π, a kernelization algorithm is a polynomial-time pre-processing procedure that transforms an arbitrary instance of π into an equivalent one whose size depends only on the input parameter(s). The resulting instance is called a problem kernel. In this paper, a kernelization algorithm for the 3-Hitting Set problem is presented along with a general kernelization for d -Hitting Set. For 3-Hitting Set, an arbitrary instance is reduced into an equivalent one that contains at most 5k2+k elements. This kernelization is an improvement over previously known methods that guarantee cubic-order kernels. Our method is used also to obtain quadratic kernels for several other problems. For a constant d⩾3, a kernelization of d -Hitting Set is achieved by a non-trivial generalization of the 3-Hitting Set method, and guarantees a kernel whose order does not exceed (2d−1)kd−1+k. en_US
dc.language.iso en en_US
dc.title A kernelization algorithm for d-Hitting Set en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Journal of Computer and System Sciences en_US
dc.journal.volume 76 en_US
dc.journal.issue 7 en_US
dc.article.pages 524-531 en_US
dc.keywords Fixed-parameter algorithms en_US
dc.keywords Hitting Set en_US
dc.keywords Kernelization en_US
dc.keywords Crown decomposition en_US
dc.keywords Vertex cover en_US
dc.keywords Hypergraphs References en_US
dc.identifier.doi http://dx.doi.org/10.1016/j.jcss.2009.09.002 en_US
dc.identifier.ctation Abu-Khzam, F. N. (2010). A kernelization algorithm for d-hitting set. Journal of Computer and System Sciences, 76(7), 524-531. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S0022000009000786
dc.orcid.id https://orcid.org/0000-0001-5221-8421

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account