Title
A Fast Branching Algorithm for Cluster Vertex Deletion.
Abstract
In the family of clustering problems we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques). Hüffner et al. (Theory Comput. Syst. (1), 196–217, ) initiated the parameterized study of , where the allowed modification is vertex deletion, and presented an elegant -time fixed-parameter algorithm, parameterized by the solution size. In the last 5 years, this algorithm remained the fastest known algorithm for and, thanks to its simplicity, became one of the textbook examples of an application of the iterative compression principle. In our work we break the 2-barrier for and present an -time branching algorithm. We achieve this improvement by a number of structural observations which we incorporate into the algorithm’s branching steps.
Year
DOI
Venue
2014
https://doi.org/10.1007/s00224-015-9631-7
Theory of Computing Systems \/ Mathematical Systems Theory
Keywords
DocType
Volume
Fixed-parameter algorithms,Cluster vertex deletion,Branching
Conference
58
Issue
ISSN
Citations 
2
1432-4350
14
PageRank 
References 
Authors
0.66
27
4
Name
Order
Citations
PageRank
Anudhyan Boral1141.00
Marek Cygan255640.52
Tomasz Kociumaka321738.57
Marcin Pilipczuk443647.86