Universität zu Köln

Fanghänel, Diana and Liers, Frauke (2010). A Fast Exact Algorithm for the Problem of Optimum Cooperation and Structure of Its Solutions. Journal of Combinatorial Optimization, 19 (3). pp. 369-393. Springer Verlag.

Preview

PDF zaik2008-574.pdf - Submitted Version Download (253kB) | Preview

Abstract

Given a graph 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 with nodes in the same class plus the number of the classes of the partition. The problem is also known in the literature as the optimum attack problem in networks. Furthermore, a relevant physics application exists. In this work, we present a fast exact algorithm for the optimum cooperation problem. Algorithms known in the literature require n-1 minimum cut computations in a corresponding network, where n is the number of nodes in the graph. By theoretical considerations and appropriately designed heuristics, we considerably reduce the numbers of minimum cut computations that are necessary in practice. We show the effectiveness of our method by presenting results on instances coming from the physics application. Furthermore, we analyze the structure of the optimal solutions.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Fanghänel, Diana UNSPECIFIED UNSPECIFIED UNSPECIFIED Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549772
Journal or Publication Title:	Journal of Combinatorial Optimization
Volume:	19
Number:	3
Page Range:	pp. 369-393
Date:	2010
Publisher:	Springer Verlag
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/54977