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 条
[41]   Fixed-Parameter Algorithms for Unsplittable Flow Cover [J].
Cristi, Andres ;
Mari, Mathieu ;
Wiese, Andreas .
THEORY OF COMPUTING SYSTEMS, 2023, 67 (01) :89-124
[42]   Fixed-Parameter Algorithms for Unsplittable Flow Cover [J].
Andrés Cristi ;
Mathieu Mari ;
Andreas Wiese .
Theory of Computing Systems, 2023, 67 :89-124
[43]   FIXED-PARAMETER ALGORITHMS FOR MAXIMUM AGREEMENT FORESTS [J].
Whidden, Chris ;
Beiko, Robert G. ;
Zeh, Norbert .
SIAM JOURNAL ON COMPUTING, 2013, 42 (04) :1431-1466
[44]   FIXED-PARAMETER ALGORITHMS FOR FINDING AGREEMENT SUPERTREES [J].
Fernandez-Baca, David ;
Guillemot, Sylvain ;
Shutters, Brad ;
Vakati, Sudheer .
SIAM JOURNAL ON COMPUTING, 2015, 44 (02) :384-410
[45]   Fixed-Parameter Algorithms for Cluster Vertex Deletion [J].
Hueffner, Falk ;
Komusiewicz, Christian ;
Moser, Hannes ;
Niedermeier, Rolf .
THEORY OF COMPUTING SYSTEMS, 2010, 47 (01) :196-217
[46]   Ubiquitous parameterization - Invitation to fixed-parameter algorithms [J].
Niedermeier, R .
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS, 2004, 3153 :84-103
[47]   Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms [J].
Gottlob, Georg ;
Greco, Gianluigi ;
Scarcello, Francesco .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2018, 94 :11-40
[48]   Fixed-Parameter Algorithms for Unsplittable Flow Cover [J].
Cristi, Andres ;
Mari, Mathieu ;
Wiese, Andreas .
37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
[49]   Fixed-parameter algorithms for cluster vertex deletion [J].
Hueffner, Falk ;
Komusiewicz, Christian ;
Moser, Hannes ;
Niedermeier, Rolf .
LATIN 2008: THEORETICAL INFORMATICS, 2008, 4957 :711-722
[50]   Fixed-Parameter and Approximation Algorithms for PCA with Outliers [J].
Dahiya, Yogesh ;
Fomin, Fedor ;
Panolan, Fahad ;
Simonov, Kirill .
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 139, 2021, 139
12345