The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
From MaRDI portal
Publication:3499737
DOI10.1007/11847250_18zbMath1154.68421MaRDI QIDQ3499737
Michael R. Fellows, Kevin Burrage, Frances A. Rosamond, Michael A. Langston, Vladimir Estivill-Castro, Shev mac
Publication date: 3 June 2008
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11847250_18
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms, On the small cycle transversal of planar graphs, Kernel bounds for disjoint cycles and disjoint paths, Quadratic kernelization for convex recoloring of trees, The complexity ecology of parameters: An illustration using bounded max leaf number, A cubic kernel for feedback vertex set and loop cutset, On problems without polynomial kernels, Kernelization – Preprocessing with a Guarantee, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, A Quartic Kernel for Pathwidth-One Vertex Deletion, A Linear Kernel for Planar Feedback Vertex Set