On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
From MaRDI portal
Cites work
- A linear-time approximation algorithm for the weighted vertex cover problem
- A Subexponential Parameterized Algorithm for Proper Interval Completion
- Algorithmic graph theory and perfect graphs
- An approximate kernel for connected feedback vertex set
- Chordal editing is fixed-parameter tractable
- Contracting few edges to remove forbidden induced subgraphs
- Edge-contraction problems
- Exploring the subexponential complexity of completion problems
- Faster parameterized algorithms for deletion to split graphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 6862097 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Interval deletion is fixed-parameter tractable
- Kernelization. Theory of parameterized preprocessing
- Linear recognition of almost interval graphs
- Lossy kernelization
- Lossy kernels for connected dominating set on sparse graphs
- Lossy kernels for graph contraction problems
- Lossy Kernels for Hitting Subgraphs
- Obtaining a bipartite graph by contracting few edges
- Obtaining planarity by contracting few edges
- Obtaining split graphs by edge contraction
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- On the NP-hardness of edge-deletion and -contraction problems
- On the parameterized complexity of approximating dominating set
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Parameterized algorithms
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Parametrized complexity theory.
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- Subexponential parameterized algorithm for minimum fill-in
- Subexponential parameterized algorithm for {\textsc{Interval Completion}}
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
Cited in
(5)- Edge contractions in subclasses of chordal graphs
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- scientific article; zbMATH DE number 1953095 (Why is no real title available?)
- On the Parameterized Complexity of Maximum Degree Contraction Problem.
- On the parameterized complexity of maximum degree contraction problem
This page was built for publication: On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6084414)
