Pseudo-Kernelization
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. Ps...
Saved in:
| Main Author: | |
|---|---|
| Format: | article |
| Published: |
2007
|
| Online Access: | http://hdl.handle.net/10725/2770 http://dx.doi.org/10.1007/s00224-007-1344-0 http://link.springer.com/article/10.1007/s00224-007-1344-0 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513459362725888 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author_facet | Abu-Khzam, Faisal N. |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. |
| dc.date.none.fl_str_mv | 2007 2015-12-07T08:53:44Z 2015-12-07T08:53:44Z 2015-12-07 |
| dc.identifier.none.fl_str_mv | 1432-4350 http://hdl.handle.net/10725/2770 http://dx.doi.org/10.1007/s00224-007-1344-0 Abu-Khzam, F. N. (2007). Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems. Theory of Computing Systems, 41(3), 399-410. http://link.springer.com/article/10.1007/s00224-007-1344-0 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Theory of Computing Systems |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Pseudo-Kernelization A Branch-then-Reduce Approach for FPT Problems |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_486221d9fd3a027cd6e0fa7b52a76bf5 |
| identifier_str_mv | 1432-4350 Abu-Khzam, F. N. (2007). Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems. Theory of Computing Systems, 41(3), 399-410. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/2770 |
| publishDate | 2007 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Pseudo-KernelizationA Branch-then-Reduce Approach for FPT ProblemsAbu-Khzam, Faisal N.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.PublishedN/A2015-12-07T08:53:44Z2015-12-07T08:53:44Z20072015-12-07Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article1432-4350http://hdl.handle.net/10725/2770http://dx.doi.org/10.1007/s00224-007-1344-0Abu-Khzam, F. N. (2007). Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems. Theory of Computing Systems, 41(3), 399-410.http://link.springer.com/article/10.1007/s00224-007-1344-0enTheory of Computing Systemsinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/27702018-05-21T09:00:07Z |
| spellingShingle | Pseudo-Kernelization Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Pseudo-Kernelization |
| title_full | Pseudo-Kernelization |
| title_fullStr | Pseudo-Kernelization |
| title_full_unstemmed | Pseudo-Kernelization |
| title_short | Pseudo-Kernelization |
| title_sort | Pseudo-Kernelization |
| url | http://hdl.handle.net/10725/2770 http://dx.doi.org/10.1007/s00224-007-1344-0 http://link.springer.com/article/10.1007/s00224-007-1344-0 |