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

U. Faigle, Walter Kern, Daniël Paulusma

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)

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.
Original languageUndefined
Pages (from-to)23-38
Number of pages15
JournalMathematical methods of operations research
Volume2000
Issue number52
DOIs
Publication statusPublished - 2000

Keywords

  • Spanning tree
  • least core
  • Cooperative game
  • METIS-140627
  • Nucleolus
  • IR-85186
  • NP-hard

Cite this