Computing the nucleolus of min-cost spanning tree games is NP-hard

U. Faigle, Walter Kern, Jeroen Kuipers

Research output: Contribution to journalArticleAcademicpeer-review

42 Citations (Scopus)

Abstract

We prove that computing the nucleolus of minimum cost spanning tree games is in general NP-hard. The proof uses a reduction from minimum cover problems.
Original languageUndefined
Pages (from-to)443-450
Number of pages8
JournalInternational journal of game theory
Volume27
Issue number3
DOIs
Publication statusPublished - 1998

Keywords

  • IR-85184
  • METIS-140790

Cite this