Linear Kernelizations for Restricted 3-Hitting Set Problems

Simple item page
dc.creatorCai, Xuan
dc.date2008-09-01
dc.date2008-09-20
dc.date.accessioned2026-07-07T10:03:50Z
dc.date.available2026-07-07T10:03:50Z
dc.descriptionThe 3-\textsc{Hitting Set} problem is also called the \textsc{Vertex Cover} problem on 3-uniform hypergraphs. In this paper, we address kernelizations of the \textsc{Vertex Cover} problem on 3-uniform hypergraphs. We show that this problem admits a linear kernel in three classes of 3-uniform hypergraphs. We also obtain lower and upper bounds on the kernel size for them by the parametric duality.
dc.description12 pages
dc.identifierhttps://arxiv.org/abs/0809.0257
dc.identifierhttp://arxiv.org/abs/0809.0257
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/169442
dc.subjectComputational Complexity
dc.subjectF.1.3
dc.titleLinear Kernelizations for Restricted 3-Hitting Set Problems
dc.typetext

Files

Collections

arXiv