An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem

DOI10.1007/s10878-015-9969-4zbMath1361.90065OpenAlexW2501188539MaRDI QIDQ511682

Li-Hsuan Chen, Bang Ye Wu

Publication date: 22 February 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9969-4

zbMATH Keywords

exact algorithmparameterized algorithmgraph modificationcluster graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• A \(2k\) kernel for the cluster editing problem
• Graph-based data clustering with overlaps
• Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
• Improved upper bounds for vertex cover
• Cluster editing with locally bounded modifications
• Graph-modeled data clustering: Exact algorithms for clique generation
• Fixed-parameter enumerability of cluster editing and related problems
• Fixed-parameter algorithms for cluster vertex deletion
• A kernelization algorithm for \(d\)-hitting set
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• A general method to speed up fixed-parameter-tractable algorithms
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Even faster parameterized cluster deletion and cluster editing
• Iterative compression and exact algorithms
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• A measure & conquer approach for the analysis of exact algorithms
• Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms
• A Fast Branching Algorithm for Cluster Vertex Deletion