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

U. Faigle, Walter Kern, Daniël Paulusma

Research output: Book/ReportReportProfessional

124 Downloads (Pure)

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
Place of PublicationEnschede
PublisherUniversiteit Twente
Number of pages17
ISBN (Print)0169-2690
Publication statusPublished - 1999

Publication series

NameMemorandum / Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
No.1483
ISSN (Print)0169-2690

Keywords

  • EWI-3303
  • MSC-90C27
  • METIS-141273
  • IR-65672
  • MSC-90D12

Cite this