An approximation algorithm for the \(l\)-pseudoforest deletion problem

DOI10.1016/j.tcs.2019.08.009zbMath1436.68252OpenAlexW2965668089WikidataQ127401893 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

zbMATH Keywords

approximation algorithmlocal ratiofeedback vertex set problem\(l\)-pseudoforest deletion problem

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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

This page was built for publication: An approximation algorithm for the \(l\)-pseudoforest deletion problem