Chordal Deletion Is Fixed-Parameter Tractable
From MaRDI portal
Publication:3522940
DOI10.1007/11917496_4zbMath1167.68412OpenAlexW1568090154MaRDI QIDQ3522940
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
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) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (14)
Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ On listing, sampling, and counting the chordal graphs with edge constraints ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ Parameterizing above or below guaranteed values ⋮ A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ Dynamically maintaining split graphs ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Induced packing of odd cycles in planar graphs
This page was built for publication: Chordal Deletion Is Fixed-Parameter Tractable
