| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428102 | Information Processing Letters | 2009 | 9 Pages |
Abstract
In this paper, we study the 3-Hitting Set problem, also called the Vertex Cover problem on 3-uniform hypergraphs. We provide linear kernelizations for this problem and its dual problem in three types of 3-uniform hypergraphs. Moreover, we obtain lower bounds on the kernel size for them by the parametric duality technique.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
