Improved algorithms for the feedback vertex set problems Conference Paper

abstract

• We present improved parameterized algorithms for the Feedback Vertex Set problem on both unweighted and weighted graphs. Both algorithms run in time O(5kkn2). The algorithms construct a feedback vertex set of size bounded by k (in the weighted case this set is of minimum weight among the feedback vertex set of size at most k) in a given graph G, or reports that no such a feedback vertex set exists in G. Springer-Verlag Berlin Heidelberg 2007.

name of conference

• Algorithms and Data Structures, 10th International Workshop, WADS 2007, Halifax, Canada, August 15-17, 2007, Proceedings

authors

• Chen, Jianer

published proceedings

• ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS

author list (cited authors)

• Chen, J., Fomin, F. V., Liu, Y., Lu, S., & Villanger, Y.

complete list of authors

• Chen, Jianer||Fomin, Fedor V||Liu, Yang||Lu, Songjian||Villanger, Yngve

publication date

• December 2007

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 10

• 3540739483

International Standard Book Number (ISBN) 13

• 978-3-540-73948-7

start page

• 422

end page

• +

volume

• 4619