A Linear Kernel for Planar Feedback Vertex Set

DOI10.1007/978-3-540-79723-4_16zbMath1142.68451OpenAlexW1491784324WikidataQ59567707 ScholiaQ59567707MaRDI QIDQ3503587

Eelko Penninkx, Hans L. Bodlaender

Publication date: 5 June 2008

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

Full work available at URL: https://doi.org/10.1007/978-3-540-79723-4_16

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Safe Approximation and Its Relation to Kernelization ⋮ A Retrospective on (Meta) Kernelization ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ Connecting face hitting sets in planar graphs ⋮ Towards optimal kernel for connected vertex cover in planar graphs ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ A linear kernel for a planar connected dominating set ⋮ A cubic kernel for feedback vertex set and loop cutset ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ On the small cycle transversal of planar graphs ⋮ Bidimensionality and Kernels ⋮ Kernelization: New Upper and Lower Bound Techniques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the feedback vertex set problem for a planar graph
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Quasi-planar graphs have a linear number of edges
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Parametrized complexity theory.
• New upper bounds on the decomposability of planar graphs
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Polynomial-time data reduction for dominating set
• A Cubic Kernel for Feedback Vertex Set
• Improved Algorithms for the Feedback Vertex Set Problems
• ON DISJOINT CYCLES
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Parameterized and Exact Computation
• Dynamic Programming and Fast Matrix Multiplication
• Algorithms – ESA 2005
• Computing and Combinatorics
• Exact Computation of Maximum Induced Forest

This page was built for publication: A Linear Kernel for Planar Feedback Vertex Set