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

Diana Fanghänel () and Frauke Liers ()
Additional contact information
Diana Fanghänel: Universität zu Köln
Frauke Liers: Universität zu Köln

Journal of Combinatorial Optimization, 2010, vol. 19, issue 3, No 7, 369-393

Abstract: Abstract Given a graph G=(V,E) with edge weights w e ∈ℝ, 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.

Keywords: Optimum attack problem; Submodular function minimization; Potts glass with many states (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9208-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:19:y:2010:i:3:d:10.1007_s10878-009-9208-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9208-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().