A Linear Kernel for Planar Feedback Vertex Set

DOI10.1007/978-3-540-79723-4_16zbMath1142.68451WikidataQ59567707 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

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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