Universität zu Köln

Fanghänel, Diana and Liers, Frauke (2008). A Fast Exact Algorithm for the Optimum Cooperation Problem. Working Paper.

Preview

PDF zaik2008-571.pdf Download (187kB) | Preview

Abstract

Given a graph G=(V,E) with real edge weights, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of the edges having nodes in the same partition plus the number of resulting partitions. The problem is also known in the literature as the optimum attack problem in networks. It occurs as a subproblem in the separation of partition inequalities. Furthermore, a relevant physics application exists. Solution algorithms known in the literature require at least |V|-1 minimum cut computations in a corresponding network. In this work, we present a fast exact algorithm for the optimum cooperation problem. By graph-theoretic considerations and appropriately designed heuristics, we considerably reduce the number of minimum cut computations that are necessary in practice. We show the effectiveness of our method by comparing the performance of our algorithm with that of the fastest previously known method on instances coming from the physics application.

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Fanghänel, Diana UNSPECIFIED UNSPECIFIED UNSPECIFIED Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549284
Date:	2008
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54928