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^{*}(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 (4)

• Graph-Theoretic Concepts in Computer Science
• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• Parameterized algorithms for cluster vertex deletion on degree-4 graphs and general graphs
• Structural parameterization of cluster deletion

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)