A faster parameterized algorithm for pseudoforest deletion

DOI10.1016/j.dam.2017.10.018zbMath1377.05184OpenAlexW2773143269WikidataQ59567341 ScholiaQ59567341MaRDI QIDQ1693129

Hans L. Bodlaender, Yota Otachi, Hirotaka Ono

Publication date: 11 January 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.10.018

zbMATH Keywords

treewidthfixed parameter tractabilitygraph algorithmsfeedback vertex setpseudoforest

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An improved deterministic parameterized algorithm for cactus vertex deletion, Parameterized orientable deletion, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, Minimizing Maximum Unmet Demand by Transportations Between Adjacent Nodes Characterized by Supplies and Demands, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, Transportation Problem Allowing Sending and Bringing Back, Fixed parameterized algorithms for generalized feedback vertex set problems, Improved FPT Algorithms for Deletion to Forest-Like Structures., Faster deterministic algorithm for cactus vertex deletion, FPT algorithms for generalized feedback vertex set problems

Cites Work

• Unnamed Item
• Reduction algorithms for graphs of small treewidth
• Faster deterministic \textsc{Feedback Vertex Set}
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Faster Computation of Path-Width
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
• Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
• Fourier meets M\"{o}bius: fast subset convolution
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• A faster parameterized algorithm for pseudoforest deletion
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth