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 Proceedings

Abstract

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
PublisherSpringer
Pages13-24
Number of pages12
ISBN (Electronic)978-3-540-39101-2
ISBN (Print)978-3-540-39098-5
DOIs
Publication statusPublished - 2006
Externally publishedYes

Publication series

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

Cite this

Dehne, F., Langston, M. A., Luo, X., Pitre, S., Shaw, P., & Zhang, Y. (2006). The cluster editing problem: Implementations and experiments. In H. L. Bodlaender, & M. A. Langston (Eds.), IWPEC: International Workshop on Parameterized and Exact Computation (pp. 13-24). (Lecture Notes in Computer Science; Vol. 4169). Springer. https://doi.org/10.1007/11847250_2