Cluster deletion revisited

DOI10.1016/J.IPL.2021.106171MaRDI QIDQ2234801zbMATH OpenOpenAlexFDO

Authors Dekel Tsur

Publication date 19 October 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.08399

zbMATH Keywords

graph algorithmsparameterized complexitybranching algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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^{\ast }(1.404^k)$.

Recommendations

• Faster parameterized algorithm for cluster vertex deletion
• Even faster parameterized cluster deletion and cluster editing
• scientific article; zbMATH DE number 2011849
• The cluster deletion problem for cographs
• Graph-modeled data clustering: Exact algorithms for clique generation

Cites work

• Automated generation of search tree algorithms for hard graphs modification problems
• Bounded-degree techniques accelerate some parameterized graph algorithms
• Even faster parameterized cluster deletion and cluster editing
• Graph-modeled data clustering: Exact algorithms for clique generation

Cited in

(16)

• The cluster deletion problem for cographs
• Graph-Theoretic Concepts in Computer Science
• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
• Parameterized algorithms for cluster vertex deletion on degree-4 graphs and general graphs
• Kernel for \(K_t\)\textsc-free Edge Deletion
• Even faster parameterized cluster deletion and cluster editing
• On the Parameterized Complexity of Clique Elimination Distance
• Cluster deletion on interval graphs and split related graphs
• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
• Cluster deletion on interval graphs and split related graphs
• Structural parameterization of cluster deletion
• A new approximate cluster deletion algorithm for diamond-free graphs
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem

This page was built for publication: Cluster deletion revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234801)