A Fast Exact Algorithm for the Optimum Cooperation Problem

Fanghänel, Diana and Liers, Frauke (2008) A Fast Exact Algorithm for the Optimum Cooperation Problem.
Technical Report , 14 p.


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.

Download: [img] PDF
Download (187kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2008-571
Depositing User: Diana Fanghänel
Date Deposited: 10 Mar 2008 00:00
Last Modified: 09 Jan 2012 16:05
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/571