Bivariate complexity analysis of \textsc{Almost Forest Deletion}

DOI10.1016/j.tcs.2017.10.021zbMath1382.68122OpenAlexW2766381797MaRDI QIDQ1686068

Saket Saurabh, Ashutosh Rai

Publication date: 20 December 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.10.021

zbMATH Keywords

parameterized complexitybivariate analysisalmost forest deletion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Unnamed Item ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ Faster deterministic algorithm for cactus vertex deletion ⋮ FPT algorithms for generalized feedback vertex set problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Implicit branching and parameterized partial cover problems
• Finding odd cycle transversals.
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Linearity of grid minors in treewidth with applications through bidimensionality
• The node-deletion problem for hereditary properties is NP-complete
• Treewidth. Computations and approximations
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Subexponential algorithms for partial cover problems
• Faster deterministic \textsc{Feedback Vertex Set}
• Parametrized complexity theory.
• Hitting Forbidden Minors: Approximation and Kernelization
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Parameterized and Exact Computation
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen

This page was built for publication: Bivariate complexity analysis of \textsc{Almost Forest Deletion}