Improved Algorithms for the Feedback Vertex Set Problems

DOI10.1007/978-3-540-73951-7_37zbMATH Open1170.68653OpenAlexW1516576670MaRDI QIDQ3603546FDOQ3603546

Authors Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger, Jianer Chen

Publication date 17 February 2009

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

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_37

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Recommendations

• Improved algorithms for feedback vertex set problems
• An improved exact algorithm for undirected feedback vertex set
• An Improved Exact Algorithm for Undirected Feedback Vertex Set
• An improved parameterized algorithm for the independent feedback vertex set problem
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• Parameterized and Exact Computation
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• FPT algorithms for generalized feedback vertex set problems
• A polyhedral approach to the feedback vertex set problem
• An improved FPT algorithm for independent feedback vertex set

Cited in

(26)

• FPT algorithms for connected feedback vertex set
• Almost 2-SAT is fixed-parameter tractable
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• A tabu search heuristic based on \(k\)-diamonds for the weighted feedback vertex set problem
• Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
• Algorithms and Data Structures
• Parameterized and Exact Computation
• Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
• Mim-width. II. The feedback vertex set problem
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• scientific article; zbMATH DE number 970357 (Why is no real title available?)
• scientific article; zbMATH DE number 7286685 (Why is no real title available?)
• A polyhedral approach to the feedback vertex set problem
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Minimum Weighted Feedback Vertex Set on Diamonds
• Parameterized and Exact Computation
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
• Deterministic Algorithms for the Independent Feedback Vertex Set Problem
• Computing and Combinatorics
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• Improved algorithms for feedback vertex set problems
• A Fixed-Parameter Enumeration Algorithm for the Weighted FVS Problem
• An Improved Exact Algorithm for Undirected Feedback Vertex Set
• Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
• A Linear Kernel for Planar Feedback Vertex Set

This page was built for publication: Improved Algorithms for the Feedback Vertex Set Problems

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