Improved algorithms for feedback vertex set problems

被引：84

作者：

Chen, Jianer ^{[2
]}

Fomin, Fedor V. ^{[1
]}

Liu, Yang ^{[2
]}

Lu, Songjian ^{[2
]}

Villanger, Yngve ^{[1
]}

机构：

[1] Univ Bergen, Dept Informat, N-5020 Bergen, Norway

[2] Texas A&M Univ, Dept Comp Sci, College Stn, TX 77843 USA

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2008年 / 74卷 / 07期

基金：

美国国家科学基金会;

关键词：

Parameterized complexity; Feedback vertex set;

D O I：

10.1016/j.jcss.2008.05.002

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present improved parameterized algorithms for the FEEDBACK VERTEX SET problem on both unweighted and weighted graphs. Both algorithms run in time O(5(k)kn(2)). 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. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：1188 / 1198

页数：11

共 19 条

[1]

[Anonymous], 1994, OPERATING SYSTEM CON

[2] A 2-approximation algorithm for the undirected feedback vertex set problem [J].

Bafna, V ;

Berman, P ;

Fujito, T .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) :289-297

[3] Randomized algorithms for the loop cutset problem [J].

Becker, A ;

Bar-Yehuda, R ;

Geiger, D .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2000, 12 :219-234

[4]

Bodlaender H. L., 1994, International Journal of Foundations of Computer Science, V5, P59, DOI 10.1142/S0129054194000049

[5]

CHEN J, 2008, ALGORITHMIC IN PRESS

[6]

Chen J, 2008, ACM S THEORY COMPUT, P177

[7]

Cormen T. H., 2001, Introduction to Algorithms, V2nd

[8]

Dehne F, 2005, LECT NOTES COMPUT SC, V3595, P859, DOI 10.1007/11533719_87

[9]

DOWNEY R, 1999, PARAMETERIZED COMPLE

[10]

Downey R. G., 1992, COMPLEXITY THEORY CU, P191

← 1 2 →