Paper Info
Title
A Quadratic Kernel for 3-Set Packing
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.
Year
DOI
Venue
2009
10.1007/978-3-642-02017-9_11
TAMC
Keywords
Field
DocType
arbitrary instance,improved kernel,3-set packing problem,equivalent instance,set packing problem,problem kernel,improved kernelization,kernelization algorithm,quadratic kernel,input parameter,reduced instance,kernelization,set packing
Kernelization,Kernel (linear algebra),Discrete mathematics,Combinatorics,Parameterized complexity,Packing problems,Quadratic equation,Quadratic function,Set packing,Mathematics,Bounded function
Conference
Volume
ISSN
Citations 
5532
0302-9743
2
PageRank 
References 
Authors
0.46
7
1
Name
Order
Citations
PageRank
Faisal N. Abu Khzam140436.25