Faster parameterized algorithm for Cluster Vertex Deletion
classification
💻 cs.DS
keywords
deletionclustervertexalgorithmgraphverticescliquecomponent
read the original abstract
In the Cluster Vertex Deletion problem the input is a graph $G$ and an integer $k$. The goal is to decide whether there is a set of vertices $S$ of size at most $k$ such that the deletion of the vertices of $S$ from $G$ results a graph in which every connected component is a clique. We give an algorithm for Cluster Vertex Deletion whose running time is $O^*(1.811^k)$.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
l-path vertex cover is easier than l-hitting set for small l
Gives FPT algorithms for l-path vertex cover achieving bases 3.945, 4.947 and 5.951 for l=5,6,7.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.