A quadratic kernel for feedback vertex set

MaRDI QIDQ4633817zbMATH OpenFDO

Authors Stéphan Thomassé

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496783

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A 4k^2 kernel for feedback vertex set
• A Cubic Kernel for Feedback Vertex Set
• A cubic kernel for feedback vertex set and loop cutset
• An improved kernel for the undirected planar feedback vertex set problem
• A new linear kernel for undirected planar feedback vertex set: smaller and simpler

Cited in

(21)

• On problems without polynomial kernels
• A randomized polynomial kernel for subset feedback vertex set
• Backdoors to tractable answer set programming
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• A Cubic Kernel for Feedback Vertex Set
• Kernelization: new upper and lower bound techniques
• Confronting intractability via parameters
• An improved kernel for the undirected planar feedback vertex set problem
• An approximate kernel for connected feedback vertex set
• Linear-time kernelization for feedback vertex set
• A naive algorithm for feedback vertex set
• A new linear kernel for undirected planar feedback vertex set: smaller and simpler
• A linear kernel for a planar connected dominating set
• On the small cycle transversal of planar graphs
• Quadratic vertex kernel for split vertex deletion
• Kernelization for feedback vertex set via elimination distance to a forest
• Kernelization for feedback vertex set via elimination distance to a forest
• A 4k^2 kernel for feedback vertex set
• On parameterized independent feedback vertex set
• Roman cycle hitting set
• A cubic kernel for feedback vertex set and loop cutset

This page was built for publication: A quadratic kernel for feedback vertex set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633817)