Finding a Minimum Feedback Vertex Set in Time \mathcal{O} (1.7548ⁿ)

DOI10.1007/11847250_17MaRDI QIDQ3499736zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Serge Gaspers, Artem 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

zbMATH Keywords

exact exponential algorithmmaximum induced forestminimum feedback vertex set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited in

(15)

• 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
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• 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

This page was built for publication: Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$

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