A \(2k\) kernel for the cluster editing problem

DOI10.1016/j.jcss.2011.04.001zbMath1238.68062MaRDI QIDQ414871

Jie Meng, Jian'er Chen

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.04.001

zbMATH Keywords

NP-hard problem; cluster editing; kernelization; parameterized computation; critical clique

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Parameterized Dynamic Cluster Editing, Cluster Editing, Your rugby mates don't need to know your colleagues: triadic closure with edge colors, \((1,1)\)-cluster editing is polynomial-time solvable, A survey of parameterized algorithms and the complexity of edge modification, On the parameterized complexity of s-club cluster deletion problems, On the parameterized complexity of \(s\)-club cluster deletion problems, A fast branching algorithm for cluster vertex deletion, On making directed graphs transitive, Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions, A faster algorithm for the cluster editing problem on proper interval graphs, An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem, Cluster editing with locally bounded modifications, Obtaining split graphs by edge contraction, Sufficient conditions for edit-optimal clusters, A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing, Parameterizing edge modification problems above lower bounds, A golden ratio parameterized algorithm for cluster editing, A simple and improved parameterized algorithm for bicluster editing, (Sub)linear kernels for edge modification problems toward structured graph classes, A new temporal interpretation of cluster editing, Parameterized dynamic cluster editing, Kernels for packing and covering problems, On the complexity of multi-parameterized cluster editing, Parameterized algorithms for min-max 2-cluster editing, A cubic-vertex kernel for flip consensus tree, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, Kernel for \(K_t\)\textsc{-free Edge Deletion}

Cites Work

• Unnamed Item
• Unnamed Item
• Correlation clustering
• Graph-modeled data clustering: Exact algorithms for clique generation
• A more effective linear kernelization for cluster editing
• Going weighted: parameterized algorithms for cluster editing
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Clustering with qualitative information
• The Cluster Editing Problem: Implementations and Experiments
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Efficient Parameterized Preprocessing for Cluster Editing