Computer Science – Data Structures and Algorithms
Scientific paper
2010-08-25
Computer Science
Data Structures and Algorithms
Scientific paper
Kernelization algorithms for the {\sc 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 {\it critical cliques}. In this paper, we present new observations and new techniques for the study of kernelization algorithms for the {\sc cluster editing} problem. Our techniques are based on the study of the relationship between {\sc cluster editing} and graph edge-cuts. As an application, we present an ${\cal O}(n^2)$-time algorithm that constructs a $2k$ kernel for the {\it weighted} version of the {\sc cluster editing} problem. Our result meets the best kernel size for the unweighted version for the {\sc cluster editing} problem, and significantly improves the previous best kernel of quadratic size for the weighted version of the problem.
Cao Yixin
Chen Jianer
No associations
LandOfFree
Cluster Editing: Kernelization based on Edge Cuts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Cluster Editing: Kernelization based on Edge Cuts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cluster Editing: Kernelization based on Edge Cuts will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-525214