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

Share/Save/Bookmark

Faigle, U. and Kern, W. and Paulusma, D. (1999) Note on the computational complexity of least core concepts for min-cost spanning tree games. [Report]

[img]
Preview
PDF
108Kb
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 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.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65672
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 141273