Abstract
Kernelization algorithms for the cluster editing problem have been a popular topic in the recent research in parameterized computation. Most kernelization algorithms for the 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 a simple algorithm that constructs a 2k-vertex kernel for the integral-weighted version of the cluster editing problem. Our result matches the best kernel bound for the unweighted version of the cluster editing problem, and significantly improves the previous best kernel bound for the weighted version of the problem. For the more general real-weighted version of the problem, our techniques lead to a simple kernelization algorithm that constructs a kernel of at most 4k vertices.
Original language | English |
---|---|
Pages (from-to) | 152-169 |
Number of pages | 18 |
Journal | Algorithmica |
Volume | 64 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Sept 2012 |
Externally published | Yes |
Keywords
- Bioinformatics
- Cluster editing
- Edge-cut
- Kernelization
- Parameterized computation
ASJC Scopus subject areas
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics