The cluster editing problem: Implementations and experiments
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 . Our experiments show that the best results are obtained by using the refined branching method in  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.
|Organisation||School of Computer Science|
Dehne, F, Langston, M.A. (Michael A.), Luo, X. (Xuemei), Pitre, S, Shaw, P. (Peter), & Zhang, Y. (Yun). (2006). The cluster editing problem: Implementations and experiments.