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 Boral | 1 | 14 | 1.00 |
Marek Cygan | 2 | 556 | 40.52 |
Tomasz Kociumaka | 3 | 217 | 38.57 |
Marcin Pilipczuk | 4 | 436 | 47.86 |