Cluster Editing: Kernelization based on Edge Cuts

Details Cluster Editing: Kernelization based on Edge Cuts Cluster Editing: Kernelization based on Edge Cuts

2010-08-25

arxiv.org/abs/1008.4250v3

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-525214