A \(13k\)-kernel for planar feedback vertex set via region decomposition
From MaRDI portal
Publication:306250
DOI10.1016/j.tcs.2016.05.031zbMath1348.68290arXiv1410.8336OpenAlexW1829289780MaRDI QIDQ306250
Publication date: 31 August 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1410.8336
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
Splitting plane graphs to outerplanarity ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics
Cites Work
- Unnamed Item
- Unnamed Item
- Planar graph vertex partition for linear problem kernels
- Improved linear problem kernel for planar connected dominating set
- Adjacency queries in dynamic sparse graphs
- A cubic kernel for feedback vertex set and loop cutset
- Towards optimal kernel for connected vertex cover in planar graphs
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- A Linear Kernel for Planar Feedback Vertex Set
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging
- An Improved Kernel for the Undirected Planar Feedback Vertex Set Problem
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Reducibility among Combinatorial Problems
- A New Linear Kernel for Undirected Planar Feedback Vertex Set: Smaller and Simpler
- Bidimensionality and Geometric Graphs
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
This page was built for publication: A \(13k\)-kernel for planar feedback vertex set via region decomposition
