A quadratic kernel for 3-set packing

Abu-Khzam, Faisal N.

A quadratic kernel for 3-set packing

Abu-Khzam, Faisal N.

URI: http://hdl.handle.net/10725/5403

URL: https://link.springer.com/chapter/10.1007/978-3-642-02017-9_11

DOI: http://dx.doi.org/110.1007/978-3-642-02017-9_11

Date: 2017-03-20

Terms of Use: This item is made available under the terms and conditions applicable to " Conference Paper / Proceeding ", as set forth at: http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php

Abstract:

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.

Citation:

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.