An improved kernel for the undirected planar feedback vertex set problem

DOI10.1007/978-3-642-33293-7_25MaRDI QIDQ4899259zbMATH OpenOpenAlexFDO

Authors

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33293-7_25

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A new linear kernel for undirected planar feedback vertex set: smaller and simpler
• A Linear Kernel for Planar Feedback Vertex Set
• A quadratic kernel for feedback vertex set
• A 13k-kernel for planar feedback vertex set via region decomposition
• A \(14k\)-kernel for planar feedback vertex set via region decomposition

Cited in

(12)

• A Linear Kernel for Planar Feedback Vertex Set
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• A \(14k\)-kernel for planar feedback vertex set via region decomposition
• A Cubic Kernel for Feedback Vertex Set
• Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
• A 13k-kernel for planar feedback vertex set via region decomposition
• A cubic kernel for feedback vertex set and loop cutset
• A 4k^2 kernel for feedback vertex set
• A new linear kernel for undirected planar feedback vertex set: smaller and simpler
• Two-layer planarization parameterized by feedback edge set
• Improved kernel results for some FPT problems based on simple observations
• A quadratic kernel for feedback vertex set

This page was built for publication: An improved kernel for the undirected planar feedback vertex set problem

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