Skip to content Skip to main navigation Report an accessibility issue

EECS Publication

An O(2O(k)) FPT Algorithm for the Undirected Feedback Vertex Set Problem

Frank Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond and Kim Stevens

We describe an algorithm for the FEEDBACK VERTEX SET problem on undirected graphs, parameterized by the size k of the feedback vertex set, that runs in time O(c^k n^3) where c = 10.567 and n is the number of vertices in the graph.

Published  2005-11-05 05:00:00  as  ut-cs-05-567 (ID:169)

ut-cs-05-567.pdf

« Back to Listing