Applied Bioinformatics Group

A   A   A
Home > Publications > Exact Algorithms for Cluster Editing: Evaluation and Experiments

Skip to content. | Skip to navigation

Sebastian Böcker, Sebastian Briesemeister, and Gunnar W Klau (2008)

Exact Algorithms for Cluster Editing: Evaluation and Experiments

In: Proc. of Workshop on Experimental Algorithms (WEA 2008), vol. 5038, pp. 289–302, Springer. Lect. Notes Comput. Sc..

We present empirical results for the Cluster Editing problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of |V|. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying k <= 25 |V|. In addition to the fastest known fixed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modifications. For the first time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques.

Printable file