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 (2008)

Going Weighted: Parameterized Algorithms for Cluster Editing

In: Proc. of Conference on Combinatorial Optimization and Applications (COCOA 2008), vol. 5165, pp. 1-12, Springer. Lect. Notes Comput. Sc..

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 surprisingly simple branching strategy for Cluster Editing. We generalize the problem assuming that edge insertion and deletion costs are positive integers. We show that the resulting search tree has size O(1.82^k ) for edit cost k, resulting in the currently fastest parameterized algorithm for this problem. We have implemented and evaluated our approach, and find that it outperforms other parametrized algorithms for the problem.

Printable file