On the complexity of testing membership in the core of min-cost spanning tree games

U. Faigle; Walter Kern; Sándor P. Fekete; Winfried Hochstättler

doi:10.1007/BF01263277

On the complexity of testing membership in the core of min-cost spanning tree games

U. Faigle, Walter Kern, Sándor P. Fekete, Winfried Hochstättler

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

71 Citations (Scopus)

11 Downloads (Pure)

Abstract

LetN = {1,...,n} be a finite set of players andKN the complete graph on the node setN∪{0}. Assume that the edges ofKN have nonnegative weights and associate with each coalitionS∪N of players as costc(S) the weight of a minimal spanning tree on the node setS∪{0}. Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to beNP-complete. Given the vectorxεℜitN withx(N) =c(N). decide whether there exists a coalitionS such thatx(S) >c(S).

Original language	English
Pages (from-to)	361-366
Number of pages	6
Journal	International journal of game theory
Volume	26
Issue number	3
DOIs	https://doi.org/10.1007/BF01263277
Publication status	Published - 1997

Keywords

METIS-140782
IR-85182

Access to Document

10.1007/BF01263277

Cite this

@article{03a6e69484ab416bbebbfeb60aca2218,

title = "On the complexity of testing membership in the core of min-cost spanning tree games",

abstract = "LetN = {1,...,n} be a finite set of players andKN the complete graph on the node setN∪{0}. Assume that the edges ofKN have nonnegative weights and associate with each coalitionS∪N of players as costc(S) the weight of a minimal spanning tree on the node setS∪{0}. Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to beNP-complete. Given the vectorxεℜitN withx(N) =c(N). decide whether there exists a coalitionS such thatx(S) >c(S).",

keywords = "METIS-140782, IR-85182",

author = "U. Faigle and Walter Kern and Fekete, {S{\'a}ndor P.} and Winfried Hochst{\"a}ttler",

year = "1997",

doi = "10.1007/BF01263277",

language = "English",

volume = "26",

pages = "361--366",

journal = "International journal of game theory",

issn = "0020-7276",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - On the complexity of testing membership in the core of min-cost spanning tree games

AU - Faigle, U.

AU - Kern, Walter

AU - Fekete, Sándor P.

AU - Hochstättler, Winfried

PY - 1997

Y1 - 1997

N2 - LetN = {1,...,n} be a finite set of players andKN the complete graph on the node setN∪{0}. Assume that the edges ofKN have nonnegative weights and associate with each coalitionS∪N of players as costc(S) the weight of a minimal spanning tree on the node setS∪{0}. Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to beNP-complete. Given the vectorxεℜitN withx(N) =c(N). decide whether there exists a coalitionS such thatx(S) >c(S).

AB - LetN = {1,...,n} be a finite set of players andKN the complete graph on the node setN∪{0}. Assume that the edges ofKN have nonnegative weights and associate with each coalitionS∪N of players as costc(S) the weight of a minimal spanning tree on the node setS∪{0}. Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to beNP-complete. Given the vectorxεℜitN withx(N) =c(N). decide whether there exists a coalitionS such thatx(S) >c(S).

KW - METIS-140782

KW - IR-85182

U2 - 10.1007/BF01263277

DO - 10.1007/BF01263277

M3 - Article

SN - 0020-7276

VL - 26

SP - 361

EP - 366

JO - International journal of game theory

JF - International journal of game theory

IS - 3

ER -

On the complexity of testing membership in the core of min-cost spanning tree games

Abstract

Keywords

Access to Document

Fingerprint

Cite this