An improved FPT algorithm for almost forest deletion problem
From MaRDI portal
Publication:1751414
DOI10.1016/j.ipl.2018.03.016zbMath1457.68220OpenAlexW2794538300MaRDI QIDQ1751414
Wenjun Li, Qilong Feng, Bin Fu, Jianxin Wang, Mugang Lin, Jian'er Chen
Publication date: 25 May 2018
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2018.03.016
graph algorithmsfeedback vertex setfixed-parameter algorithmiterative compressionalmost forest deletion
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Improved PTAS for the constrained \(k\)-means problem ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ Faster deterministic algorithm for cactus vertex deletion ⋮ FPT algorithms for generalized feedback vertex set problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On feedback vertex set: new measure and new structures
- Partition on trees with supply and demand: kernelization and algorithms
- Improved kernel results for some FPT problems based on simple observations
- On parameterized independent feedback vertex set
- FPT algorithms for connected feedback vertex set
- Finding odd cycle transversals.
- Approximating maximum agreement forest on multiple binary trees
- Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Improved algorithms for feedback vertex set problems
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Faster deterministic \textsc{Feedback Vertex Set}
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Parameterized computational complexity of Dodgson and Young elections
- An Improved Exact Algorithm for Undirected Feedback Vertex Set
- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Vertex Cover Structural Parameterization Revisited
- Bivariate Complexity Analysis of Almost Forest Deletion
- Dealing with 4-Variables by Resolution: An Improved MaxSAT Algorithm
- Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
- A faster parameterized algorithm for pseudoforest deletion
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Reducibility among Combinatorial Problems
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
