Pseudo-Kernelization

Abu-Khzam, Faisal N.

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