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

被引：25

作者：

Faigle, U ^{[1
]}

Kern, W ^{[1
]}

Fekete, SP ^{[1
]}

Hochstattler, W ^{[1
]}

机构：

[1] UNIV COLOGNE,ZPR,H-50923 COLOGNE,GERMANY

来源：

INTERNATIONAL JOURNAL OF GAME THEORY | 1997年 / 26卷 / 03期

关键词：

cooperative game; core; spanning tree; NP-complete; X3C;

D O I：

10.1007/s001820050039

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

Let N = {1,...,n} be a finite set of players and K-N the complete graph on the node set N boolean OR {0}. Assume that the edges of K-N have nonnegative weights and associate with each coalition S subset of or equal to N of players as cost c(S) the weight of a minimal spanning tree on the node set S boolean OR {0}. Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to be NP-complete. Given the vector x is an element of R-N with x(N) = c(N). decide whether there exists a coalition S such that x(S) > c(S).

引用

页码：361 / 366

页数：6

共 16 条

[1]

Aarts H., 1993, ZOR, Methods and Models of Operations Research, V38, P163, DOI 10.1007/BF01414212

[2]

AARTS H, 1994, THESIS U TWENTE ENSC

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[4] COST ALLOCATION FOR A SPANNING TREE - GAME THEORETIC APPROACH [J].

BIRD, CG .

NETWORKS, 1976, 6 (04) :335-350

[5]

CHVATAL V, 1978, SOCS789 MCGILL U SCH

[6]

Claus A., 1973, Networks, V3, P289, DOI [10.1002/net.3230030402, DOI 10.1002/NET.3230030402]

[7] ON THE COMPLEXITY OF COOPERATIVE SOLUTION CONCEPTS [J].

DENG, XT ;

PAPADIMITRIOU, CH .

MATHEMATICS OF OPERATIONS RESEARCH, 1994, 19 (02) :257-266

[8]

Edmonds J., 1970, COMBINATORIAL STRUCT, P69, DOI DOI 10.1007/3-540-36478

[9] THE RELATIONSHIP BETWEEN CONVEX GAMES AND MINIMUM COST SPANNING TREE GAMES - A CASE FOR PERMUTATIONALLY CONVEX GAMES [J].

GRANOT, D ;

HUBERMAN, G .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (03) :288-292

[10] MINIMUM COST SPANNING TREE GAMES [J].

GRANOT, D ;

HUBERMAN, G .

MATHEMATICAL PROGRAMMING, 1981, 21 (01) :1-18

← 1 2 →