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, 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, 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