Cluster deletion revisited

DOI10.1016/J.IPL.2021.106171zbMATH Open1476.05191arXiv1907.08399OpenAlexW3185869980MaRDI QIDQ2234801FDOQ2234801

Authors: Dekel Tsur 

Publication date: 19 October 2021

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

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)$.

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

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

zbMATH Keywords

graph algorithmsparameterized complexitybranching algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• 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
• 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)