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

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

0.00 Avg rating0 Votes
Article ID: iaor20013519
Country: Germany
Volume: 52
Issue: 1
Start Page Number: 23
End Page Number: 38
Publication Date: Jan 2000
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: , ,
Keywords: networks
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.

Reviews

Required fields are marked *. Your email address will not be published.