Skip to main content

Research Repository

Advanced Search

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

Faigle, U.; Kern, W.; Paulusma, D.

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


Authors

U. Faigle

W. Kern



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.

Citation

Faigle, U., Kern, W., & Paulusma, D. (2000). Note on the computational complexity of least core concepts for min-cost spanning tree games. Mathematical Methods of Operations Research, 52(1), 23-38. https://doi.org/10.1007/s001860000059

Journal Article Type Article
Publication Date Sep 1, 2000
Deposit Date Oct 13, 2009
Publicly Available Date Mar 29, 2024
Journal Mathematical Methods of Operations Research
Print ISSN 1432-2994
Electronic ISSN 1432-5217
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 52
Issue 1
Pages 23-38
DOI https://doi.org/10.1007/s001860000059
Keywords Cooperative game, Least core, Nucleolus, Spanning tree, NP-hard.
Public URL https://durham-repository.worktribe.com/output/1525312

Files





You might also like



Downloadable Citations