Deterministic Algorithms for the Independent Feedback Vertex Set Problem

DOI10.1007/978-3-319-19315-1_31MaRDI QIDQ2946071zbMATH OpenOpenAlexFDO

Authors Yuma Tamura, Takehiro Ito, Xiao Zhou

Publication date 15 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19315-1_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• An improved parameterized algorithm for the independent feedback vertex set problem
• On parameterized independent feedback vertex set
• On parameterized independent feedback vertex set
• Approximability of the independent feedback vertex set problem for bipartite graphs
• Approximability of the independent feedback vertex set problem for bipartite graphs
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Fixed parameterized algorithms for generalized feedback vertex set problems
• Parameterized and Exact Computation
• Improved Algorithms for the Feedback Vertex Set Problems

Cites work

• scientific article; zbMATH DE number 6118220 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1953101 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A \(c^k n\) 5-approximation algorithm for treewidth
• Algorithmic meta-theorems for restrictions of treewidth
• An improved parameterized algorithm for the independent feedback vertex set problem
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Graph Classes: A Survey
• Graph minors. II. Algorithmic aspects of tree-width
• Linear-time modular decomposition of directed graphs
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• On parameterized independent feedback vertex set
• Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm

Cited in

(14)

• Feedback vertex set on planar graphs
• An improved parameterized algorithm for the independent feedback vertex set problem
• Independent feedback vertex sets for graphs of bounded diameter
• An improved FPT algorithm for independent feedback vertex set
• An improved FPT algorithm for independent feedback vertex set
• Minimum feedback vertex set and acyclic coloring.
• Recognizing Graphs Close to Bipartite Graphs
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Independent Feedback Vertex Set for P_5-free Graphs
• Efficient algorithm for minimum feedback vertex set problem on trapezoid graphs
• Independent feedback vertex set for \(P_5\)-free graphs
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• Approximability of the independent feedback vertex set problem for bipartite graphs
• A feedback vertex set of 2-degenerate graphs

This page was built for publication: Deterministic Algorithms for the Independent Feedback Vertex Set Problem

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