A quadratic kernel for 3-set packing
We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces an equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. Such parameterized reductions are known as kernelization algorithms, and each reduced...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | conferenceObject |
| منشور في: |
2017
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/5403 http://dx.doi.org/110.1007/978-3-642-02017-9_11 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-642-02017-9_11 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513476279402496 |
|---|---|
| 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 | 2017-03-20T09:23:32Z 2017-03-20T09:23:32Z 2017-03-20 |
| dc.identifier.none.fl_str_mv | 978-3-642-02017-9 http://hdl.handle.net/10725/5403 http://dx.doi.org/110.1007/978-3-642-02017-9_11 Abu-Khzam, F. N. (2009, May). A quadratic kernel for 3-set packing. In International Conference on Theory and Applications of Models of Computation (pp. 81-87). Springer Berlin Heidelberg. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-642-02017-9_11 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Springer |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | A quadratic kernel for 3-set packing Theory and Applications of Models of Computation |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces an equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. Such parameterized reductions are known as kernelization algorithms, and each reduced instance is called a problem kernel. Our result improves on previously known kernelizations and can be generalized to produce improved kernels for the r-Set Packing problem whenever r is a fixed constant. Improved kernelization for r-Dimensional-Matching can also be inferred. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_8a80598f8dfcf46e98dadcfcc2225a97 |
| identifier_str_mv | 978-3-642-02017-9 Abu-Khzam, F. N. (2009, May). A quadratic kernel for 3-set packing. In International Conference on Theory and Applications of Models of Computation (pp. 81-87). Springer Berlin Heidelberg. |
| 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/5403 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | Springer |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | A quadratic kernel for 3-set packingTheory and Applications of Models of ComputationAbu-Khzam, Faisal N.We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces an equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. Such parameterized reductions are known as kernelization algorithms, and each reduced instance is called a problem kernel. Our result improves on previously known kernelizations and can be generalized to produce improved kernels for the r-Set Packing problem whenever r is a fixed constant. Improved kernelization for r-Dimensional-Matching can also be inferred.N/ASpringer2017-03-20T09:23:32Z2017-03-20T09:23:32Z2017-03-20Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObject978-3-642-02017-9http://hdl.handle.net/10725/5403http://dx.doi.org/110.1007/978-3-642-02017-9_11Abu-Khzam, F. N. (2009, May). A quadratic kernel for 3-set packing. In International Conference on Theory and Applications of Models of Computation (pp. 81-87). Springer Berlin Heidelberg.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://link.springer.com/chapter/10.1007/978-3-642-02017-9_11eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/54032021-03-19T10:03:24Z |
| spellingShingle | A quadratic kernel for 3-set packing Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | A quadratic kernel for 3-set packing |
| title_full | A quadratic kernel for 3-set packing |
| title_fullStr | A quadratic kernel for 3-set packing |
| title_full_unstemmed | A quadratic kernel for 3-set packing |
| title_short | A quadratic kernel for 3-set packing |
| title_sort | A quadratic kernel for 3-set packing |
| url | http://hdl.handle.net/10725/5403 http://dx.doi.org/110.1007/978-3-642-02017-9_11 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-642-02017-9_11 |