Kernelization algorithms for the cluster editing problem have been a popular topic in the recent research in parameterized computation. Thus far most kernelization algorithms for this problem are based on the concept of critical cliques. In this paper, we present new observations and new techniques for the study of kernelization algorithms for the cluster editing problem. Our techniques are based on the study of the relationship between cluster editing and graph edge-cuts. As an application, we present an O(n2)-time algorithm that constructs a 2k kernel for the weighted version of the cluster editing problem. Our result meets the best kernel size for the unweighted version for the cluster editing problem, and significantly improves the previous best kernel of quadratic size for the weighted version of the problem.
|Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|5th International Symposium on Parameterized and Exact Computation, IPEC 2010
|13/12/10 → 15/12/10
- Theoretical Computer Science
- General Computer Science