An improved FPT algorithm for almost forest deletion problem

DOI10.1016/j.ipl.2018.03.016zbMath1457.68220OpenAlexW2794538300WikidataQ130062712 ScholiaQ130062712MaRDI 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

zbMATH Keywords

graph algorithmsfeedback vertex setfixed-parameter algorithmiterative compressionalmost forest deletion

Mathematics Subject Classification ID

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 (6)

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

This page was built for publication: An improved FPT algorithm for almost forest deletion problem