Improved algorithms for feedback vertex set problems Academic Article

abstract

• We present improved parameterized algorithms for the feedback vertex set problem on both unweighted and weighted graphs. Both algorithms run in time O (5k k n2). The algorithms construct a feedback vertex set of size at most k (in the weighted case this set is of minimum weight among the feedback vertex sets of size at most k) in a given graph G of n vertices, or report that no such feedback vertex set exists in G. 2008 Elsevier Inc. All rights reserved.

authors

• Chen, Jianer

published proceedings

• JOURNAL OF COMPUTER AND SYSTEM SCIENCES

altmetric score

• 3

author list (cited authors)

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

citation count

• 88

complete list of authors

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

publication date

• November 2008

publisher

• Elsevier  Publisher

published in

• Journal of Computer and System Sciences  Journal

keywords

• Feedback Vertex Set
• Parameterized Complexity

Digital Object Identifier (DOI)

• 10.1016/j.jcss.2008.05.002

start page

• 1188

end page

• 1198

volume

• 74

issue

• 7

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.jcss.2008.05.002