Improved Algorithms for the Feedback Vertex Set Problems

DOI10.1007/978-3-540-73951-7_37MaRDI QIDQ3603546zbMATH OpenOpenAlexFDO

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)

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

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)