Note on the computational complexity of least core concepts for min-cost spanning tree games

Faigle, Ulrich and Kern, Walter and Paulusma, D. (2000) Note on the computational complexity of least core concepts for min-cost spanning tree games.
Published in: Mathematical methods of operations research Vol. 52 (1). pp. 23-38.

Abstract

Various least core concepts including the classical least core of cooperative games are discussed. By a reduction from minimum cover problems, we prove that computing an element in these least cores is in general NP-hard for minimum cost spannning tree games. As a consequence, computing the nucleolus, the nucleon and the per-capita nucleolus of minimum cost spanning tree games is also NP-hard.


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