Faigle, U. and Kern, W. and Paulusma, Daniel (2000) 'Note on the computational complexity of least core concepts for min-cost spanning tree games.', Mathematical methods of operations research., 52 (1). pp. 23-38.
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.
|Keywords:||Cooperative game, Least core, Nucleolus, Spanning tree, NP-hard.|
|Full text:||PDF - Accepted Version (90Kb)|
|Publisher Web site:||http://dx.doi.org/10.1007/s001860000059|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/s001860000059|
|Record Created:||13 Oct 2009 11:35|
|Last Modified:||08 Jan 2015 15:12|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|