An improved parameterized algorithm for the independent feedback vertex set problem

DOI10.1016/j.tcs.2014.03.031zbMath1419.05205arXiv1308.0085MaRDI QIDQ2447761

Yinglei Song

Publication date: 29 April 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.0085

zbMATH Keywords

dynamic programming; parameterized algorithm; independent feedback vertex set

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

90C39: Dynamic programming

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Deterministic Algorithms for the Independent Feedback Vertex Set Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On parameterized independent feedback vertex set
• Finding odd cycle transversals.
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• On two techniques of combining branching and treewidth
• Faster deterministic \textsc{Feedback Vertex Set}
• Fixed-parameter tractability results for feedback set problems in tournaments
• Parameterized complexity of Vertex Cover variants
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• On Feedback Vertex Set New Measure and New Structures
• ON DISJOINT CYCLES
• Reducibility among Combinatorial Problems
• Parameterized and Exact Computation
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Computing and Combinatorics
• Exact Computation of Maximum Induced Forest