LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.date.accessioned 2015-12-07T08:53:44Z
dc.date.available 2015-12-07T08:53:44Z
dc.date.copyright 2007
dc.date.issued 2015-12-07
dc.identifier.issn 1432-4350 en_US
dc.identifier.uri http://hdl.handle.net/10725/2770
dc.description.abstract Pseudo-kernelization is introduced in this paper as a new strategy for improving fixed-parameter algorithms. This new technique works for bounded search tree algorithms by identifying favorable branching conditions whose absence could be used to reduce the size of corresponding problem instances. Pseudo-kernelization applies well to hitting set problems. It can be used either to improve the search tree size of a 3-Hitting-Set algorithm from O*(2.179k) to O*(2.05k), or to improve the kernel size from k3 to 27k. In this paper the parameterized 3-Hitting-Set and Face Cover problems are used as typical examples. en_US
dc.language.iso en en_US
dc.title Pseudo-Kernelization en_US
dc.type Article en_US
dc.description.version Published en_US
dc.title.subtitle A Branch-then-Reduce Approach for FPT Problems 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 Theory of Computing Systems en_US
dc.journal.volume 41 en_US
dc.journal.issue 3 en_US
dc.article.pages 399-410 en_US
dc.identifier.doi http://dx.doi.org/10.1007/s00224-007-1344-0 en_US
dc.identifier.ctation Abu-Khzam, F. N. (2007). Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems. Theory of Computing Systems, 41(3), 399-410. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://link.springer.com/article/10.1007/s00224-007-1344-0
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