Cluster deletion revisited

07/19/2019

∙

by   Dekel Tsur, et al.

∙

0

∙

share

In the Cluster Deletion problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k edges whose removal from G results a graph in which every connected component is a clique. In this paper we give an algorithm for Cluster Deletion whose running time is O^*(1.404^k).