2006-01-01
The cluster editing problem: Implementations and experiments
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| Citation |
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.
|