An improved kernel for the undirected planar feedback vertex set problem

DOI10.1007/978-3-642-33293-7_25zbMATH Open1374.68237OpenAlexW1855543298MaRDI QIDQ4899259FDOQ4899259

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

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

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)

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
• A quadratic kernel for feedback vertex set
• Improved kernel results for some FPT problems based on simple observations

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)