# 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).

Download: |
Postscript
- Preprinted Version
Download (120kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

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 |