Dekel Tsur
Senior Academic
Cluster deletion revisited
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 in 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.404k).
| Publication language | English |
| Journal | Information Processing Letters |
| Volume | 173 |
| Publication status | Published - 01.01.2022 |
| Article Number | 106171 |
Keywords
Branching algorithms
Graph algorithms
Parameterized complexity
ASJC Scopus subject areas
Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications
