Bivariate Complexity Analysis of Almost Forest Deletion

DOI10.1007/978-3-319-21398-9_11zbMath1465.68109OpenAlexW1148234532MaRDI QIDQ3196379

Ashutosh Rai, Saket Saurabh

Publication date: 29 October 2015

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-21398-9_11

Mathematics Subject Classification ID

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

Related Items (3)

Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem

Cites Work

• 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
• The node-deletion problem for hereditary properties is NP-complete
• Quickly excluding a planar graph
• Treewidth. Computations and approximations
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Subexponential algorithms for partial cover problems
• Faster deterministic \textsc{Feedback Vertex Set}
• Parametrized complexity theory.
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Parameterized and Exact Computation
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen

This page was built for publication: Bivariate Complexity Analysis of Almost Forest Deletion