KLUEDO RSS FeedNeueste Dokumente / Latest documents
https://kluedo.ub.uni-kl.de/index/index/
Fri, 19 Dec 2008 12:48:05 +0100Fri, 19 Dec 2008 12:48:05 +0100Minimum Cut Tree Games
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2049
In this paper we introduce a cooperative game based on the minimum cut tree problem which is also known as multi-terminal maximum flow problem. Minimum cut tree games are shown to be totally balanced and a solution in their core can be obtained in polynomial time. This special core allocation is closely related to the solution of the original graph theoretical problem. We give an example showing that the game is not supermodular in general, however, it is for special cases and for some of those we give an explicit formula for the calculation of the Shapley value.Anne M. Schwahnreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2049Fri, 19 Dec 2008 12:48:05 +0100New heuristics for the minimum fundamental cut basis problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1887
Given an undirected connected network and a weight function finding a basis of the cut space with minimum sum of the cut weights is termed Minimum Cut Basis Problem. This problem can be solved, e.g., by the algorithm of Gomory and Hu [GH61]. If, however, fundamentality is required, i.e., the basis is induced by a spanning tree T in G, the problem becomes NP-hard. Theoretical and numerical results on that topic can be found in Bunke et al. [BHMM07] and in Bunke [Bun06]. In the following we present heuristics with complexity O(m log n) and O(mn), where n and m are the numbers of vertices and edges respectively, which obtain upper bounds on the aforementioned problem and in several cases outperform the heuristics of Schwahn [Sch05].Alexander J. Perez Tchernov; Anne M. Schwahnpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1887Tue, 24 Jul 2007 14:31:16 +0200