Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
From MaRDI portal
Publication:3499736
DOI10.1007/11847250_17zbMath1154.05327MaRDI QIDQ3499736
Serge Gaspers, Fedor V. Fomin, Artem V. Pyatkin
Publication date: 3 June 2008
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11847250_17
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs, Unnamed Item, MIP formulations for induced graph optimization problems: a tutorial, Robust networked multiagent optimization: designing agents to repair their own utility functions, Extremal properties of the bipartite vertex frustration of graphs, Improved algorithms for feedback vertex set problems, Solving connected dominating set faster than \(2^n\), Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles, On the minimum feedback vertex set problem: Exact and enumeration algorithms, A cubic kernel for feedback vertex set and loop cutset, An improved FPT algorithm for almost forest deletion problem, Fixed-parameter tractability for subset feedback set problems with parity constraints, A Moderately Exponential Time Algorithm for Full Degree Spanning Tree, A Linear Kernel for Planar Feedback Vertex Set, Iterative Compression for Exactly Solving NP-Hard Minimization Problems