The cluster editing problem: Implementations and experiments

F Dehne, M.A. Langston, X. Luo, S. Pitre, P. Shaw, Y Zhang

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for "yes" instances with increasing values of k.
Original languageUndefined
Title of host publicationIWPEC
Subtitle of host publicationInternational Workshop on Parameterized and Exact Computation
EditorsHans L. Bodlaender, Michael A. Langston
Number of pages12
ISBN (Electronic)978-3-540-39101-2
ISBN (Print)978-3-540-39098-5
Publication statusPublished - 2006
Externally publishedYes

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743

Cite this