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

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 spanning 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. Copyright Springer-Verlag Berlin Heidelberg 2000

MoreLess

Year of publication:	2000
Authors:	Faigle, Ulrich ; Kern, Walter ; Paulusma, Daniël
Published in:	Mathematical Methods of Operations Research. - Springer. - Vol. 52.2000, 1, p. 23-38
Publisher:	Springer
Subject:	cooperative game \| least core \| nucleolus \| spanning tree \| NP-hard

More details

Extent:	text/html
Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010999970