Improved fixed-parameter algorithms for two feedback set problems

被引：0
作者：
Guo, J
Gramm, J
Hüffner, F
Niedermeier, R
Wernicke, S
机构：
[1] Univ Jena, Inst Informat, D-07743 Jena, Germany
[2] Univ Tubingen, Wilhelm Schickard Inst Informat, D-72076 Tubingen, Germany
来源：
ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS | 2005年 / 3608卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Settling a ten years open question, we show that the NP-complete FEEDBACK VERTEX SET problem is deterministically solvable in O(c(k) center dot m) time, where m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. As a second result, we present a fixed-parameter algorithm for the NP-complete EDGE BIPARTIZATION problem with runtime O(2(k) center dot m(2)).
引用
收藏
页码：158 / 168
页数：11
相关论文
共 50 条
  • [21] Fixed-parameter algorithms in phylogenetics
    Gramm, Jens
    Nickelsen, Arfst
    Tantau, Till
    COMPUTER JOURNAL, 2008, 51 (01) : 79 - 101
  • [22] Faster fixed-parameter tractable algorithms for matching and packing problems
    Fellows, M. R.
    Knauer, C.
    Nishimura, N.
    Ragde, P.
    Rosamond, F.
    Stege, U.
    Thilikos, D. M.
    Whitesides, S.
    ALGORITHMICA, 2008, 52 (02) : 167 - 176
  • [23] Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems
    M. R. Fellows
    C. Knauer
    N. Nishimura
    P. Ragde
    F. Rosamond
    U. Stege
    D. M. Thilikos
    S. Whitesides
    Algorithmica, 2008, 52 : 167 - 176
  • [24] Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
    Dom, Michael
    Guo, Jiong
    Niedermeier, Rolf
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2010, 76 (3-4) : 204 - 221
  • [25] Faster fixed-parameter tractable algorithms for matching and packing problems
    Fellows, MR
    Knauer, C
    Nishimura, N
    Ragde, P
    Rosamond, F
    Stege, U
    Thilikos, DM
    Whitesides, S
    ALGORITHMS ESA 2004, PROCEEDINGS, 2004, 3221 : 311 - 322
  • [26] Two fixed-parameter tractable algorithms for testing upward planarity
    Healy, Patrick
    Lynch, Karol
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2006, 17 (05) : 1095 - 1114
  • [27] Fixed-parameter algorithms for the cocoloring problem
    Campos, Victor
    Klein, Sulamita
    Sampaio, Rudini
    Silva, Ana
    DISCRETE APPLIED MATHEMATICS, 2014, 167 : 52 - 60
  • [28] Two fixed-parameter algorithms for vertex covering by paths on trees
    Guo, Jiong
    Niedermeier, Rolf
    Uhlmann, Johannes
    INFORMATION PROCESSING LETTERS, 2008, 106 (02) : 81 - 86
  • [29] Techniques for practical fixed-parameter algorithms
    Hueffner, Falk
    Niedermeier, Rolf
    Wernicke, Sebastian
    COMPUTER JOURNAL, 2008, 51 (01) : 7 - 25
  • [30] Fixed-parameter algorithms for Kemeny Scores
    Betzler, Nadja
    Fellows, Michael R.
    Guo, Jiong
    Niedermeier, Rolf
    Rosamond, Frances A.
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2008, 5034 : 60 - +
12345