caa a22 4500 445804599 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9339-7 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9339-7 Exact Algorithms for Cluster Editing: Evaluation and Experiments [Elektronische Daten] [Sebastian Böcker, Sebastian Briesemeister, Gunnar Klau] The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques. We present empirical results for this 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 $\lvert V\rvert$ , where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying $k\leq25\lvert V\rvert$ . 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. (A preliminary version of this paper appeared under the title "Exact algorithms for cluster editing: Evaluation and experiments” in the Proceedings of the 7th Workshop on Experimental Algorithms, WEA 2008, in: LNCS, vol.5038, Springer, pp. 289-302.) Springer Science+Business Media, LLC, 2009 Cluster editing nationallicence Algorithm engineering nationallicence Computer experiments nationallicence NP-complete problem nationallicence Fixed-parameter tractability nationallicence FPT nationallicence Integer linear programming nationallicence ILP nationallicence Branch-and-cut algorithm nationallicence Böcker Sebastian Institut für Informatik, Friedrich-Schiller-Universität Jena, Jena, Germany aut Briesemeister Sebastian Div. for Simulation of Biological Systems, ZBIT/WSI, Eberhard Karls Universität Tübingen, Tübingen, Germany aut Klau Gunnar CWI, P.O. Box 94079, 1090 GB, Amsterdam, Netherlands aut Algorithmica Springer-Verlag 60/2(2011-06-01), 316-334 0178-4617 60:2<316 2011 60 453 https://doi.org/10.1007/s00453-009-9339-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9339-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Böcker Sebastian Institut für Informatik, Friedrich-Schiller-Universität Jena, Jena, Germany aut NATIONALLICENCE 700 1- Briesemeister Sebastian Div. for Simulation of Biological Systems, ZBIT/WSI, Eberhard Karls Universität Tübingen, Tübingen, Germany aut NATIONALLICENCE 700 1- Klau Gunnar CWI, P.O. Box 94079, 1090 GB, Amsterdam, Netherlands aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 316-334 0178-4617 60:2<316 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer