Paths to trees and cacti
From MaRDI portal
Publication:5283353
DOI10.1007/978-3-319-57586-5_4zbMATH Open1486.68120OpenAlexW2606694986MaRDI QIDQ5283353FDOQ5283353
Lawqueen Kanesh, Akanksha Agrawal, Saket Saurabh, Prafullkumar Tale
Publication date: 21 July 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-57586-5_4
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Finding odd cycle transversals.
- Title not available (Why is that?)
- Parameterized Algorithms
- Unit interval editing is fixed-parameter tractable
- Chordal deletion is fixed-parameter tractable
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Contracting graphs to paths and trees
- Obtaining planarity by contracting few edges
- Chordal Editing is Fixed-Parameter Tractable
- Interval Deletion Is Fixed-Parameter Tractable
- Obtaining a Bipartite Graph by Contracting Few Edges
- Subexponential Parameterized Algorithm for Minimum Fill-In
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- On the NP-hardness of edge-deletion and -contraction problems
- Edge-contraction problems
- A faster FPT algorithm for bipartite contraction
- Contracting Few Edges to Remove Forbidden Induced Subgraphs
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- Linear Recognition of Almost Interval Graphs
- A Subexponential Parameterized Algorithm for Proper Interval Completion
- A polynomial kernel for trivially perfect editing
- On the threshold of intractability
- Faster parameterized algorithms for deletion to split graphs
- Title not available (Why is that?)
- Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
- Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT
- A Subexponential Parameterized Algorithm for Proper Interval Completion
Cited In (8)
- Trees, Paths, Stars, Caterpillars and Spiders
- On the parameterized complexity of contraction to generalization of trees
- On the parameterized complexity of maximum degree contraction problem
- Contracting to a longest path in H-free graphs
- On the Parameterized Complexity of Maximum Degree Contraction Problem.
- On the parameterized complexity of grid contraction
- A single exponential-time FPT algorithm for cactus contraction
- Parameterized complexity of maximum edge colorable subgraph
This page was built for publication: Paths to trees and cacti
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283353)
