An improved kernelization algorithm for r-Set Packing
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 c...
Saved in:
| Main Author: | |
|---|---|
| Format: | article |
| Published: |
2010
|
| Online Access: | http://hdl.handle.net/10725/2781 http://dx.doi.org/10.1016/j.ipl.2010.04.020 http://www.sciencedirect.com/science/article/pii/S0020019010001018 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513459378454528 |
|---|---|
| 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 | 2010 2015-12-07T13:26:44Z 2015-12-07T13:26:44Z 2015-12-07 |
| dc.identifier.none.fl_str_mv | 0020-0190 http://hdl.handle.net/10725/2781 http://dx.doi.org/10.1016/j.ipl.2010.04.020 Abu-Khzam, F. N. (2010). An improved kernelization algorithm for r-Set Packing. Information Processing Letters, 110(16), 621-624. http://www.sciencedirect.com/science/article/pii/S0020019010001018 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Information Processing Letters |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | An improved kernelization algorithm for r-Set Packing |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_3c934cfd871e5b4faec8cff5ae45b64f |
| identifier_str_mv | 0020-0190 Abu-Khzam, F. N. (2010). An improved kernelization algorithm for r-Set Packing. Information Processing Letters, 110(16), 621-624. |
| 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/2781 |
| publishDate | 2010 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | An improved kernelization algorithm for r-Set PackingAbu-Khzam, Faisal N.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.PublishedN/A2015-12-07T13:26:44Z2015-12-07T13:26:44Z20102015-12-07Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0020-0190http://hdl.handle.net/10725/2781http://dx.doi.org/10.1016/j.ipl.2010.04.020Abu-Khzam, F. N. (2010). An improved kernelization algorithm for r-Set Packing. Information Processing Letters, 110(16), 621-624.http://www.sciencedirect.com/science/article/pii/S0020019010001018enInformation Processing Lettersinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/27812018-05-21T08:34:51Z |
| spellingShingle | An improved kernelization algorithm for r-Set Packing Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | An improved kernelization algorithm for r-Set Packing |
| title_full | An improved kernelization algorithm for r-Set Packing |
| title_fullStr | An improved kernelization algorithm for r-Set Packing |
| title_full_unstemmed | An improved kernelization algorithm for r-Set Packing |
| title_short | An improved kernelization algorithm for r-Set Packing |
| title_sort | An improved kernelization algorithm for r-Set Packing |
| url | http://hdl.handle.net/10725/2781 http://dx.doi.org/10.1016/j.ipl.2010.04.020 http://www.sciencedirect.com/science/article/pii/S0020019010001018 |