Faster Parameterized Algorithm for Cluster Vertex Deletion

被引：0
作者：
Dekel Tsur
机构：
[1] Ben-Gurion University of the Negev,
来源：
Theory of Computing Systems | 2021年 / 65卷
关键词：
Graph algorithms; Parameterized complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.811k).
引用
收藏
页码：323 / 343
页数：20
相关论文
共 33 条
[1]  
Bansal N(2004)Correlation clustering Mach. Learn. 56 89-113
[2]  
Blum A(1999)Clustering gene expression patterns J. Comput. Biol. 6 281-297
[3]  
Chawla S(2016)A fast branching algorithm for cluster vertex deletion Theory Comput. Syst. 58 357-376
[4]  
Ben-Dor A(1996)Fixed-parameter tractability of graph modification problems for hereditary properties Inf. Process. Lett. 58 171-176
[5]  
Shamir R(2016)Fixed-parameter algorithms for vertex cover P3 Discrete Optim. 19 12-22
[6]  
Yakhini Z(2010)A top-down approach to search-trees: improved algorithmics for 3-hitting set Algorithmica 57 97-118
[7]  
Boral A(2010)Iterative compression and exact algorithms Theor. Comput. Sci. 411 1045-1053
[8]  
Cygan M(2004)Automated generation of search tree algorithms for hard graph modification problems Algorithmica 39 321-347
[9]  
Kociumaka T(2010)Fixed-parameter algorithms for cluster vertex deletion Theory Comput. Syst. 47 196-217
[10]  
Pilipczuk M(2016)A faster FPT algorithm for 3-path vertex cover Inf. Process. Lett. 116 273-278
1234