An approximation algorithm for the \(l\)-pseudoforest deletion problem
From MaRDI portal
Publication:2285146
DOI10.1016/j.tcs.2019.08.009zbMath1436.68252WikidataQ127401893 ScholiaQ127401893MaRDI QIDQ2285146
Jianxin Wang, Qilong Feng, Bin Fu, Mugang Lin
Publication date: 16 January 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2019.08.009
approximation algorithm; local ratio; feedback vertex set problem; \(l\)-pseudoforest deletion problem
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- Kernelization and randomized parameterized algorithms for co-path set problem
- 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
- A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- An improved FPT algorithm for almost forest deletion problem
- Faster deterministic \textsc{Feedback Vertex Set}
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- An improved exact algorithm for undirected feedback vertex set
- Dealing with several parameterized problems by random methods
- Parameterized algorithms for edge biclique and related problems
- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
- Bivariate Complexity Analysis of Almost Forest Deletion
- A faster parameterized algorithm for pseudoforest deletion
- Structural Parameterizations of Feedback Vertex Set
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
