On the Complexity of Testing Membership in the Core of Min-Cost Spanning Tree Games

Ulrich Faigle (), Walter Kern, Winfried Hochstättler and Sándor P. Fekete
Additional contact information
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

International Journal of Game Theory, 1997, vol. 26, issue 3, 366 pages

Abstract: 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)$.

Date: 1998-05-19
Note: Received May 1995 Revised version I May 1996 Revised version II June 1996
References: Add references at CitEc
Citations: View citations in EconPapers (9)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:jogath:v:26:y:1997:i:3:p:361-366

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().