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

Jeroen Kuipers (), Ulrich Faigle () and Walter Kern ()
Additional contact information
Jeroen Kuipers: Instituto de Economia Publica, Universidad del Pais Vasco, Avda. Lehen-Dakari Aguirre 83, E-48015 Bilbao, Spain
Walter Kern: Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands

International Journal of Game Theory, 1998, vol. 27, issue 3, 443-450

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.

Keywords: Nucleolus; · (search for similar items in EconPapers)
Date: 1998-11-02
Note: Received October 1997/Final version May 1998
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://link.springer.de/link/service/journals/00182/papers/8027003/80270443.pdf (application/pdf)
Access to the full text of the articles in this series is restricted

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:27:y:1998:i:3:p:443-450

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().