On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
From MaRDI portal
Publication:6084414
DOI10.4230/lipics.approx/random.2020.51OpenAlexW3081802581MaRDI QIDQ6084414
Prafullkumar Tale, Spoorthy Gunda, Saket Saurabh, Pallavi Jain, Daniel Lokshtanov
Publication date: 31 October 2023
Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.51
Related Items (2)
On the parameterized complexity of maximum degree contraction problem ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- Fundamentals of parameterized complexity
- Unit interval editing is fixed-parameter tractable
- Edge-contraction problems
- Obtaining split graphs by edge contraction
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Fixed-parameter tractability of graph modification problems for hereditary properties
- A polynomial kernel for trivially perfect editing
- On the NP-hardness of edge-deletion and -contraction problems
- Algorithmic graph theory and perfect graphs
- Obtaining planarity by contracting few edges
- On the threshold of intractability
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- Faster parameterized algorithms for deletion to split graphs
- Contracting graphs to paths and trees
- A faster FPT algorithm for bipartite contraction
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Parametrized complexity theory.
- Exploring the Subexponential Complexity of Completion Problems
- Contracting Few Edges to Remove Forbidden Induced Subgraphs
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- A linear-time approximation algorithm for the weighted vertex cover problem
- Subexponential Parameterized Algorithm for I <scp>nterval</scp> C <scp>ompletion</scp>
- Linear Recognition of Almost Interval Graphs
- Lossy Kernels for Graph Contraction Problems
- Kernelization
- Interval Deletion Is Fixed-Parameter Tractable
- Lossy kernelization
- Lossy Kernels for Hitting Subgraphs
- On the parameterized complexity of approximating dominating set
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- Obtaining a Bipartite Graph by Contracting Few Edges
- Subexponential Parameterized Algorithm for Minimum Fill-In
- Parameterized Algorithms
- A Subexponential Parameterized Algorithm for Proper Interval Completion
This page was built for publication: On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
