An improved FPT algorithm for almost forest deletion problem

DOI10.1016/J.IPL.2018.03.016MaRDI QIDQ1751414zbMATH OpenOpenAlexWikidataFDO

Authors Mugang Lin, Qilong Feng, Jianxin Wang, Bin Fu, Wen-Jun Li, Jianer 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

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• Generalized pseudoforest deletion: algorithms and uniform kernel
• Generalized pseudoforest deletion: algorithms and uniform kernel
• An approximation algorithm for the \(l\)-pseudoforest deletion problem

Cites work

• scientific article; zbMATH DE number 571325 (Why is no real title available?)
• scientific article; zbMATH DE number 1467487 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A faster parameterized algorithm for pseudoforest deletion
• An Improved Exact Algorithm for Undirected Feedback Vertex Set
• Approximating maximum agreement forest on multiple binary trees
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Dealing with 4-variables by resolution: an improved \textsc{MaxSAT} algorithm
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• FPT algorithms for connected feedback vertex set
• Faster deterministic \textsc{Feedback Vertex Set}
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• Finding odd cycle transversals.
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Generalized pseudoforest deletion: algorithms and uniform kernel
• Improved algorithms for feedback vertex set problems
• Improved kernel results for some FPT problems based on simple observations
• On feedback vertex set: new measure and new structures
• On parameterized independent feedback vertex set
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Parameterized algorithms
• Parameterized computational complexity of Dodgson and Young elections
• Partition on trees with supply and demand: kernelization and algorithms
• Reducibility among combinatorial problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Vertex cover structural parameterization revisited

Cited in

(10)

• Improved FPT Algorithms for Deletion to Forest-Like Structures.
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• FPT algorithms for generalized feedback vertex set problems
• Faster deterministic algorithm for cactus vertex deletion
• Fixed parameterized algorithms for generalized feedback vertex set problems
• An approximation algorithm for the \(l\)-pseudoforest deletion problem
• Improved FPT Algorithms for Deletion to Forest-Like Structures
• Improved PTAS for the constrained \(k\)-means problem
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• Faster parameterized algorithm for \(r\)-pseudoforest deletion

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751414)