Faster Parameterized Algorithm for Cluster Vertex Deletion

被引：13
作者：
Tsur, Dekel [1 ]
机构：
[1] Ben Gurion Univ Negev, Beer Sheva, Israel
来源：
THEORY OF COMPUTING SYSTEMS | 2021年 / 65卷 / 02期
关键词：
Graph algorithms; Parameterized complexity;
D O I：
10.1007/s00224-020-10005-w
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In the Cluster Vertex Deletion problem the input is a graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that the deletion of the vertices of S from G results in a graph in which every connected component is a clique. We give an algorithm for Cluster Vertex Deletion whose running time is O*(1.811(k)).
引用
收藏
页码：323 / 343
页数：21
相关论文
共 17 条
  • [1] Correlation clustering
    Bansal, N
    Blum, A
    Chawla, S
    [J]. MACHINE LEARNING, 2004, 56 (1-3) : 89 - 113
  • [2] Clustering gene expression patterns
    Ben-Dor, A
    Shamir, R
    Yakhini, Z
    [J]. JOURNAL OF COMPUTATIONAL BIOLOGY, 1999, 6 (3-4) : 281 - 297
  • [3] A Fast Branching Algorithm for Cluster Vertex Deletion
    Boral, Anudhyan
    Cygan, Marek
    Kociumaka, Tomasz
    Pilipczuk, Marcin
    [J]. THEORY OF COMPUTING SYSTEMS, 2016, 58 (02) : 357 - 376
  • [4] Fixed-parameter tractability of graph modification problems for hereditary properties
    Cai, LZ
    [J]. INFORMATION PROCESSING LETTERS, 1996, 58 (04) : 171 - 176
  • [5] Fixed-parameter algorithms for vertex cover P3
    Chang, Maw-Shang
    Chen, Li-Hsuan
    Hung, Ling-Ju
    Rossmanith, Peter
    Su, Ping-Chen
    [J]. DISCRETE OPTIMIZATION, 2016, 19 : 12 - 22
  • [6] Cygan M., 2015, Parameterized Algorithms, V5
  • [7] A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set
    Fernau, Henning
    [J]. ALGORITHMICA, 2010, 57 (01) : 97 - 118
  • [8] Exact Algorithms via Monotone Local Search
    Fomin, Fedor V.
    Gaspers, Serge
    Lokshtanov, Daniel
    Saurabh, Saket
    [J]. STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, : 764 - 775
  • [9] Iterative compression and exact algorithms
    Fomin, Fedor V.
    Gaspers, Serge
    Kratsch, Dieter
    Liedloff, Mathieu
    Saurabh, Saket
    [J]. THEORETICAL COMPUTER SCIENCE, 2010, 411 (7-9) : 1045 - 1053
  • [10] Automated generation of search tree algorithms for hard graph modification problems
    Gramm, J
    Guo, J
    Hüffner, F
    Niedermeier, R
    [J]. ALGORITHMICA, 2004, 39 (04) : 321 - 347
12