Linear Kernelizations for Restricted 3-Hitting Set Problems - Computer Science > Computational Complexity

Linear Kernelizations for Restricted 3-Hitting Set Problems - Computer Science > Computational Complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: The 3-\textsc{Hitting Set} problem is also called the \textsc{Vertex Cover}problem on 3-uniform hypergraphs. In this paper, we address kernelizations ofthe \textsc{Vertex Cover} problem on 3-uniform hypergraphs. We show that thisproblem admits a linear kernel in three classes of 3-uniform hypergraphs. Wealso obtain lower and upper bounds on the kernel size for them by theparametric duality.

Autor: Xuan Cai

Fuente: https://arxiv.org/