An improved kernelization algorithm for r-Set Packing

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.date.accessioned 2015-12-07T13:26:44Z
dc.date.available 2015-12-07T13:26:44Z
dc.date.copyright 2010
dc.date.issued 2015-12-07
dc.identifier.issn 0020-0190 en_US
dc.identifier.uri http://hdl.handle.net/10725/2781
dc.description.abstract We present a reduction procedure that takes an arbitrary instance of the r -Set Packing problem and produces an equivalent instance whose number of elements is in O(kr−1), where k is the input parameter. Such parameterized reductions are known as kernelization algorithms, and a reduced instance is called a problem kernel. Our result improves on previously known kernelizations by a factor of k. In particular, the number of elements in a 3-Set Packing kernel is improved from a cubic function of the parameter to a quadratic one. en_US
dc.language.iso en en_US
dc.title An improved kernelization algorithm for r-Set Packing 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 Information Processing Letters en_US
dc.journal.volume 110 en_US
dc.journal.issue 16 en_US
dc.article.pages 621-624 en_US
dc.keywords Fixed-parameter algorithms en_US
dc.keywords Kernelization en_US
dc.keywords Crown decomposition en_US
dc.keywords Set Packing en_US
dc.keywords Graph algorithms en_US
dc.identifier.doi http://dx.doi.org/10.1016/j.ipl.2010.04.020 en_US
dc.identifier.ctation Abu-Khzam, F. N. (2010). An improved kernelization algorithm for r-Set Packing. Information Processing Letters, 110(16), 621-624. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S0020019010001018
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