FPT algorithms for Connected Feedback Vertex Set

被引：0

作者：

Neeldhara Misra

Geevarghese Philip

Venkatesh Raman

Saket Saurabh

Somnath Sikdar

机构：

[1] The Institute of Mathematical Sciences,

[2] RWTH Aachen University,undefined

来源：

Journal of Combinatorial Optimization | 2012年 / 24卷

关键词：

Parameterized algorithms; FPT algorithms; Connected Feedback Vertex Set; Feedback Vertex Set; Group Steiner Tree; Steiner Tree; Directed Steiner Out-Tree; Hardness of polynomial kernelization; Subexponential FPT algorithms; H-minor-free graphs; Dynamic programming over tree decompositions;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists F⊆V, |F|≤k, such that G[V∖F] is a forest and G[F] is connected.

引用

页码：131 / 146

页数：15

共 14 条

[1] Bodlaender HL(1996)A linear-time algorithm for finding tree-decompositions of small treewidth SIAM J Comput 25 1305-1317
[2] Demaine ED(2008)Linearity of grid minors in treewidth with applications through bidimensionality Combinatorica 28 19-36
[3] Hajiaghayi M(2008)Solving connected dominating set faster than 2 Algorithmica 52 153-166
[4] Fomin FV(2006)Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization J Comput Syst Sci 72 1386-1396
[5] Grandoni F(2008)Enumerate and expand: improved algorithms for connected vertex cover and tree cover Theory Comput Syst 43 234-253
[6] Kratsch D(undefined)undefined undefined undefined undefined-undefined
[7] Guo J(undefined)undefined undefined undefined undefined-undefined
[8] Gramm J(undefined)undefined undefined undefined undefined-undefined
[9] Hüffner F(undefined)undefined undefined undefined undefined-undefined
[10] Niedermeier R(undefined)undefined undefined undefined undefined-undefined

← 1 2 →