A \(2k\) kernel for the cluster editing problem
From MaRDI portal
Publication:414871
DOI10.1016/j.jcss.2011.04.001zbMath1238.68062OpenAlexW2044452930MaRDI QIDQ414871
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
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (29)
A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Parameterizing edge modification problems above lower bounds ⋮ Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ A new temporal interpretation of cluster editing ⋮ Cluster Editing ⋮ On the complexity of multi-parameterized cluster editing ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ \((1,1)\)-cluster editing is polynomial-time solvable ⋮ Obtaining split graphs by edge contraction ⋮ On making directed graphs transitive ⋮ 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 ⋮ Sufficient conditions for edit-optimal clusters ⋮ Asymptotic bounds for clustering problems in random graphs ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Parameterized dynamic cluster editing ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ 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 ⋮ Kernels for packing and covering problems ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ A simple and improved parameterized algorithm for bicluster editing ⋮ Parameterized Dynamic Cluster Editing ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ A fast branching algorithm for cluster vertex 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
This page was built for publication: A \(2k\) kernel for the cluster editing problem
