History
Year:
-
Type:
Journal
Book
Article
Please fill in your query. A complete syntax description you will find on the General Help page.
Kernelization for cycle transversal problems. (English)
Discrete Appl. Math. 160, No. 7-8, 1224-1231 (2012).
Summary: We present new kernelization results for two problems, $s$-cycle transversal and $(\le s)$-cycle transversal, when $s$ is 4 or 5. We show that 4-cycle transversal and $\le 4$-cycle transversal admit $6k^{2}$ vertex kernels in general graphs. We then prove NP-completeness of s-cycle transversal and $(\le s)$-cycle transversal in planar graphs for $s>3$. We show the following linear vertex kernels in planar graphs ‒ a 74$k$ vertex kernel for 4-cycle transversal; a 32$k$ vertex kernel for ($\le 4$)-cycle transversal; a 266$k$ vertex kernel for ($\le 5$)-cycle transversal.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!