Repository: Freie Universität Berlin, Math Department

Evaluation of ILP-based approaches for partitioning into colorful components

Bruckner, S. and Hüffner, F. and Komusiewicz, Ch. and Niedermeier, R. (2013) Evaluation of ILP-based approaches for partitioning into colorful components. In: Experimental Algorithms. Lecture Notes in Computer Science, 7933 (7933). Springer, Heidelberg, pp. 176-187. ISBN 978-3-642-38526-1 (print) / 978-3-642-38527-8 (online)

[img] PDF - Submitted Version
Restricted to Registered users only



The NP-hard Colorful Components problem is a graph partitioning problem on vertex-colored graphs. We identify a new application of Colorful Components in the correction of Wikipedia interlanguage links, and describe and compare three exact and two heuristic approaches. In particular, we devise two ILP formulations, one based on Hitting Set and one based on Clique Partition. Furthermore, we use the recently proposed implicit hitting set framework [Karp, JCSS 2011; Chandrasekaran et al., SODA 2011] to solve Colorful Components. Finally, we study a move-based and a merge-based heuristic for Colorful Components. We can optimally solve Colorful Components for Wikipedia link correction data; while the Clique Partition-based ILP outperforms the other two exact approaches, the implicit hitting set is a simple and competitive alternative. The merge-based heuristic is very accurate and outperforms the move-based one. The above results for Wikipedia data are confirmed by experiments with synthetic instances.

Item Type:Book Section
Subjects:Mathematical and Computer Sciences
Divisions:Department of Mathematics and Computer Science > Institute of Mathematics > BioComputing Group
ID Code:1267
Deposited By: BioComp Admin
Deposited On:25 Apr 2013 10:08
Last Modified:03 Mar 2017 14:41

Repository Staff Only: item control page