Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
From MaRDI portal
Publication:2149107
DOI10.1007/s00453-022-00963-7zbMath1502.68367arXiv2009.00809OpenAlexW3081965010MaRDI QIDQ2149107
Publication date: 28 June 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2009.00809
linear programmingapproximation algorithmdistance-hereditary graphschordal graphsfeedback vertex setPtolemaic graphs
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- Parameterized complexity of vertex deletion into perfect graph classes
- Finding odd cycle transversals.
- Structure and linear time recognition of 3-leaf powers
- Chordal deletion is fixed-parameter tractable
- Laminar structure of ptolemaic graphs with applications
- On diameters and radii of bridged graphs
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Erdős-Pósa property of chordless cycles and its applications
- Error compensation in leaf power problems
- Rank-width and vertex-minors
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- Hitting Diamonds and Growing Cacti
- A characterization of ptolemaic graphs
- Computing the Minimum Fill-In is NP-Complete
- A New Algorithm for Generating All the Maximal Independent Sets
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation
- Linear Recognition of Almost Interval Graphs
- Approximation and Kernelization for Chordal Vertex Deletion
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- Compression via Matroids
- Interval Deletion Is Fixed-Parameter Tractable
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Interval Vertex Deletion Admits a Polynomial Kernel
- Losing Treewidth by Separating Subsets
- A polynomial kernel for distance-hereditary vertex deletion
This page was built for publication: Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
