Chordal Deletion Is Fixed-Parameter Tractable

DOI10.1007/11917496_4MaRDI QIDQ3522940zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• Chordal deletion is fixed-parameter tractable
• Approximation and kernelization for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Interval deletion is fixed-parameter tractable

Cited in

(29)

• Parameterized complexity of vertex deletion into perfect graph classes
• Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
• 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
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Parameterized orientable deletion
• 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
• Vertex deletion problems on chordal graphs
• Structural parameterizations with modulator oblivion
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
• scientific article; zbMATH DE number 3847425 (Why is no real title available?)
• 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

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)