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

Faigle, Ulrich and Fekete, Sandor P. and Hochstättler, Winfried and Kern, Walter (1997) On the Complexity of Testing Membership in the Core of Min-cost Spanning Tree Games.
Published in: International Journal of Game Theory Vol. 26 (3). pp. 361-366.

Abstract

Let N= {1,...,n} be a finite set of players and KN the complete graph on the node set Ncup {0}. Assume that the edges of KN 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 Èxact cover by 3-sets', which is one of the six basic NP-complete problems in the book of M. R. Garey and D. S. Johnson ['Computers and intractability. A guide to the theory of NP-completeness' (1979)] we exhibit the following problem to be NP-complete. Given the vector xin{frak R}sp N with x(N)= c(N) decide whether there exists a coalition S such that x(S)> c(S).


Actions:
Download: [img] Postscript - Preprinted Version
Download (120kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr94-166
Depositing User: Prof. Dr. Ulrich Faigle
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 09:30
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/166