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 条
  • [31] Fixed-parameter algorithms for DAG Partitioning
    van Bevern, Rene
    Bredereck, Robert
    Chopin, Morgan
    Hartung, Sepp
    Hueffner, Falk
    Nichterlein, Andre
    Suchy, Ondfej
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 220 : 134 - 160
  • [32] Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees
    Boecker, Sebastian
    Quang Bao Anh Bui
    Truss, Anke
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2012, 8 (01)
  • [33] Fixed-parameter algorithms for Kemeny rankings
    Betzler, Nadja
    Fellows, Michael R.
    Guo, Jiong
    Niedermeier, Rolf
    Rosamond, Frances A.
    [J]. THEORETICAL COMPUTER SCIENCE, 2009, 410 (45) : 4554 - 4570
  • [34] Fixed-parameter algorithms for scaffold filling
    Bulteau, Laurent
    Carrieri, Anna Paola
    Dondi, Riccardo
    [J]. THEORETICAL COMPUTER SCIENCE, 2015, 568 : 72 - 83
  • [35] Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems
    Gottlob, Georg
    Szeider, Stefan
    [J]. COMPUTER JOURNAL, 2008, 51 (03) : 303 - 325
  • [36] Improved algorithms for the feedback vertex set problems
    Chen, Jianer
    Fomin, Fedor V.
    Liu, Yang
    Lu, Songjian
    Villanger, Yngve
    [J]. ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS, 2007, 4619 : 422 - +
  • [37] Improved algorithms for feedback vertex set problems
    Chen, Jianer
    Fomin, Fedor V.
    Liu, Yang
    Lu, Songjian
    Villanger, Yngve
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (07) : 1188 - 1198
  • [38] Fixed-Parameter Algorithms for Cluster Vertex Deletion
    Falk Hüffner
    Christian Komusiewicz
    Hannes Moser
    Rolf Niedermeier
    [J]. Theory of Computing Systems, 2010, 47 : 196 - 217
  • [39] Fixed-parameter algorithms for graph constraint logic *,**
    Hatanaka, Tatsuhiko
    Hommelsheim, Felix
    Ito, Takehiro
    Kobayashi, Yusuke
    Muehlenthaler, Moritz
    Suzuki, Akira
    [J]. THEORETICAL COMPUTER SCIENCE, 2023, 959
  • [40] Fixed-Parameter Algorithms for Closed World Reasoning
    Lackner, Martin
    Pfandler, Andreas
    [J]. 20TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE (ECAI 2012), 2012, 242 : 492 - 497
12345