Chordal Deletion Is Fixed-Parameter Tractable
DOI10.1007/11917496_4zbMATH Open1167.68412OpenAlexW1568090154MaRDI QIDQ3522940FDOQ3522940
Authors: Dániel Marx 
Publication date: 4 September 2008
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.122.8670
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (29)
- Parameterized complexity of vertex deletion into perfect graph classes
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Smaller kernels for several FPT problems based on simple observations
- On listing, sampling, and counting the chordal graphs with edge constraints
- Parameterizing above or below guaranteed values
- Parameterized complexity of finding regular induced subgraphs
- Approximation and kernelization for chordal vertex deletion
- Approximation and kernelization for chordal vertex deletion
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Chordal editing is fixed-parameter tractable
- Vertex deletion problems on chordal graphs
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized orientable deletion
- Parameterized orientable deletion
- On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
- Chordal deletion is fixed-parameter tractable
- Induced packing of odd cycles in planar graphs
- Constant ratio fixed-parameter approximation of the edge multicut problem
- Dynamically maintaining split graphs
- Structural parameterizations with modulator oblivion
- Structural parameterizations with modulator oblivion
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
- Vertex deletion problems on chordal graphs
- Title not available (Why is that?)
- Chordal editing is fixed-parameter tractable
- An FPT certifying algorithm for the vertex-deletion problem
- Wheel-Free Deletion Is W[2]-Hard
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
This page was built for publication: Chordal Deletion Is Fixed-Parameter Tractable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3522940)
