A polynomial kernel for distance-hereditary vertex deletion

DOI10.1007/s00453-021-00820-zOpenAlexW2949988872MaRDI QIDQ5918311

Eun Jung Kim, O-joung Kwon

Publication date: 30 June 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

distance-hereditary graphparameterized complexitypolynomial kernelrank-width

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items

A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries ⋮ A polynomial kernel for 3-leaf power deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
• On graphs without a \(C_{4}\) or a diamond
• Distance-hereditary graphs
• On diameters and radii of bridged graphs
• The node-deletion problem for hereditary properties is NP-complete
• Matroid matching and some applications
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Rank-width and vertex-minors
• Algebraic Algorithms for Linear Matroid Parity Problems
• Graph Theory
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Uniform Kernelization Complexity of Hitting Forbidden Minors
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• Transforming trees by successive local complementations
• A Combinatorial Decomposition Theory
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Approximation and Kernelization for Chordal Vertex Deletion
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• On Independent Circuits Contained in a Graph
• Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems