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

Authors
Faigle, U Kern, W Paulusma, D
Citation
U. Faigle et al., Note on the computational complexity of least core concepts for min-cost spanning tree games, MATH M O R, 52(1), 2000, pp. 23-38
Citations number
16
Categorie Soggetti
Engineering Mathematics
Journal title
MATHEMATICAL METHODS OF OPERATIONS RESEARCH
ISSN journal
14322994 → ACNP
Volume
52
Issue
1
Year of publication
2000
Pages
23 - 38
Database
ISI
SICI code
1432-2994(200009)52:1<23:NOTCCO>2.0.ZU;2-9
Abstract
Various least core concepts including the classical least core of cooperati ve games are discussed. By a reduction from minimum cover problems, we prov e 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 ga mes is also NP-hard.