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 |
|