Applied Bioinformatics Group

A   A   A
Home > Publications > Going Weighted: Parameterized Algorithms for Cluster Editing

Skip to content. | Skip to navigation

Sebastian Böcker, Sebastian Briesemeister, Quang B Bui, and Anke Truss (2009)

Going Weighted: Parameterized Algorithms for Cluster Editing

Theoretical Computer Science, 410(52):5467-5480.

The goal of the Cluster Editing problem is to make the fewest changes to the edge set of an input graph such that the resulting graph is a disjoint union of cliques. This problem is NP-complete but recently, several parameterized algorithms have been proposed. In this paper, we present a number of surprisingly simple search tree algorithms for Weighted Cluster Editing assuming that edge insertion and deletion costs are positive integers. We show that the smallest search tree has size O(1.82^k) for edit cost k, resulting in the currently fastest parameterized algorithm, both for this problem and its unweighted counterpart. We have implemented and compared our algorithms, and achieved promising results.
This is an extended version of two articles published in the Proc. of the 6th Asia Pacific Bioinformatics Conference, APBC 2008, in: Series on Advances in Bioinformatics and Computational Biology, vol. 5, Imperial College Press, pp. 211–220; and Proc. of the 2nd Conference on Combinatorial Optimization and Applications, COCOA 2008, in: LNCS, vol. 5038, Springer, pp. 289–302.
Printable file