Computing the nucleolus of min-cost spanning tree games is NP-hard

Computing the nucleolus of min-cost spanning tree games is NP-hard

0.00 Avg rating0 Votes
Article ID: iaor2000388
Country: Germany
Volume: 27
Issue: 3
Start Page Number: 443
End Page Number: 450
Publication Date: Jan 1998
Journal: International Journal of Game Theory
Authors: , ,
Keywords: networks, computational analysis
Abstract:

We prove that computing the nucleolus of minimum cost spanning tree games is in general NP-hard. The proof uses a reduction from minimum cover problems.

Reviews

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