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:||(AM) Accepted Manuscript|
Download PDF (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|
|Date accepted:||No date available|
|Date deposited:||08 January 2015|
|Date of first online publication:||September 2000|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|