A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Fanghänel D, Liers F
Zeitschrift: Journal of Combinatorial Optimization
Verlag: Springer Verlag (Germany)
Jahr der Veröffentlichung: 2010
Band: 19
Heftnummer: 3
Seitenbereich: 369-393
ISSN: 1382-6905


Abstract


Given a graph G=(V,E) with edge weights w ℝ, 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 |V|-1 minimum cut computations in a corresponding network. 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. © 2009 Springer Science+Business Media, LLC.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)


Einrichtungen weiterer Autorinnen und Autoren

Universität zu Köln


Zitierweisen

APA:
Fanghänel, D., & Liers, F. (2010). A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions. Journal of Combinatorial Optimization, 19(3), 369-393. https://dx.doi.org/10.1007/s10878-009-9208-y

MLA:
Fanghänel, Diana, and Frauke Liers. "A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions." Journal of Combinatorial Optimization 19.3 (2010): 369-393.

BibTeX: 

Zuletzt aktualisiert 2018-23-10 um 21:50