Ulrich Faigle (Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands) Walter Kern (Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands) Winfried Hochstättler (ZPR, Zentrum für paralleles Rechnen Universität zu Köln Albertus-Magnus-Platz, H 50923 Köln, Germany) Sándor P. Fekete (ZPR, Zentrum für paralleles Rechnen Universität zu Köln Albertus-Magnus-Platz, H 50923 Köln, Germany)
Additional information is available for the following
registered author(s):
Let $N=\{ 1,...,n\} $ be a finite set of players and $K_{N}$ the complete graph on the node set $N\cup \{ 0\} $. Assume that the edges of $K_{N}$ have nonnegative weights and associate with each coalition $S\subseteq N$ of players as cost $c(S)$ the weight of a minimal spanning tree on the node set $S\cup \{ 0\} $.
Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to be NP-complete. Given the vector $x\in R^{N}$ with $x(N)=c(N)$. Decide whether there exists a coalition S such that $x(S) > c(S)$.
Download Info
To our knowledge, this item is not available for
download. To find whether it is available, there are three
options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page
whether it is in fact available.
3. Perform a search for a similarly titled item that would be
available.