Paths to trees and cacti
From MaRDI portal
Publication:1998842
DOI10.1016/j.tcs.2021.01.033zbMath1486.68121OpenAlexW3126040650MaRDI QIDQ1998842
Prafullkumar Tale, Saket Saurabh, Lawqueen Kanesh, Akanksha Agrawal
Publication date: 9 March 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.01.033
Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- Unit interval editing is fixed-parameter tractable
- Finding odd cycle transversals.
- Edge-contraction problems
- Chordal deletion is fixed-parameter tractable
- 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
- Obtaining planarity by contracting few edges
- On the threshold of intractability
- 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.
- Contracting Few Edges to Remove Forbidden Induced Subgraphs
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
- Subexponential Parameterized Algorithm for I <scp>nterval</scp> C <scp>ompletion</scp>
- Linear Recognition of Almost Interval Graphs
- Kernelization
- Interval Deletion Is Fixed-Parameter Tractable
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT
- A Near-Optimal Planarization Algorithm
- 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: Paths to trees and cacti
