A polynomial kernel for block graph deletion

DOI10.1007/s00453-017-0316-2zbMath1372.68134arXiv1506.08477OpenAlexW3022854747MaRDI QIDQ2408204

Eun Jung Kim, O-joung Kwon

Publication date: 10 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.08477

zbMATH Keywords

block graphblock decompositionfixed parameter algorithmkernelization algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Unnamed Item ⋮ Vertex deletion on split graphs: beyond 4-hitting set

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chordal editing is fixed-parameter tractable
• On feedback vertex set: new measure and new structures
• On parameterized independent feedback vertex set
• Finding odd cycle transversals.
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• Faster deterministic \textsc{Feedback Vertex Set}
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Rank-width and vertex-minors
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
• Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
• Graph minors. II. Algorithmic aspects of tree-width
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Approximation and Kernelization for Chordal Vertex Deletion
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Parameterized and Exact Computation
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen

This page was built for publication: A polynomial kernel for block graph deletion