Fixed-Parameter Algorithms for Cluster Vertex Deletion

被引：65

作者：

Hueffner, Falk ^{[1
]}

Komusiewicz, Christian ^{[1
]}

Moser, Hannes ^{[1
]}

Niedermeier, Rolf ^{[1
]}

机构：

[1] Univ Jena, Inst Informat, D-07743 Jena, Germany

来源：

THEORY OF COMPUTING SYSTEMS | 2010年 / 47卷 / 01期

关键词：

Parameterized complexity; Iterative compression; NP-hard problems; Graph algorithms; Clustering; FEEDBACK SET PROBLEMS; HITTING SET; KERNELIZATION; TRACTABILITY;

D O I：

10.1007/s00224-008-9150-x

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We initiate the first systematic study of the NP-hard CLUSTER VERTEX DELETION (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches for a minimum number of vertex deletions to transform a graph into a collection of disjoint cliques. The parameter is the number of vertex deletions. We present efficient fixed-parameter algorithms for CVD applying the fairly new iterative compression technique. Moreover, we study the variant of CVD where the maximum number of cliques to be generated is pre-specified. Here, we exploit connections to fixed-parameter algorithms for (weighted) VERTEX COVER.

引用

页码：196 / 217

页数：22

共 38 条

[1]

Abu-Khzam FN, 2007, LECT NOTES COMPUT SC, V4619, P434

[2]

Abu-Khzam FN, 2006, LECT NOTES COMPUT SC, V4169, P264

[3]

AILON N, 2005, TR71905 PRINC U DEP

[4]

Ailon Nir, 2005, P 37 ANN ACM S THEOR, P684, DOI DOI 10.1145/1060590.1060692