COMPUTING THE NUCLEOLUS OF MIN-COST SPANNING TREE GAMES IS NP-HARD

Authors
FAIGLE U KERN W KUIPERS J
Citation
U. Faigle et al., COMPUTING THE NUCLEOLUS OF MIN-COST SPANNING TREE GAMES IS NP-HARD, International journal of game theory, 27(3), 1998, pp. 443-450
Citations number
14
Categorie Soggetti
Social Sciences, Mathematical Methods",Economics,"Statistic & Probability","Mathematics, Miscellaneous","Mathematics, Miscellaneous","Statistic & Probability
Journal title
International journal of game theory → ACNP
ISSN journal
00207276
Volume
27
Issue
3
Year of publication
1998
Pages
443 - 450
Database
ISI
SICI code
0020-7276(1998)27:3<443:CTNOMS>2.0.ZU;2-O
Abstract
We prove that computing the nucleolus of minimum cost spanning tree ga mes is in general NP-hard. The proof uses a reduction from minimum cov er problems.