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

DOI10.1007/BF01263277zbMath0885.90123OpenAlexW3123101064MaRDI QIDQ1365002

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

Publication date: 22 April 1998

Published in: International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01263277

zbMATH Keywords

corecooperative gameNP-completeminimal spanning tree

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Cooperative games (91A12) Games involving graphs (91A43)

Related Items (28)

Social enterprise tree network games ⋮ A note on Steiner tree games ⋮ Generalized minimum spanning tree games ⋮ COALITION FORMATION GAMES: A SURVEY ⋮ NP-completeness in hedonic games ⋮ Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ The Least-Core and Nucleolus of Path Cooperative Games ⋮ On approximately fair cost allocation in Euclidean TSP games ⋮ Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases ⋮ Unnamed Item ⋮ Computing the least-core and nucleolus for threshold cardinality matching games ⋮ A system-theoretic model for cooperation, interaction and allocation ⋮ On the complexity of core, kernel, and bargaining set ⋮ Complexity of constructing solutions in the core based on synergies among coalitions ⋮ Enforcing fair cooperation in production-inventory settings with heterogeneous agents ⋮ Computing an element in the lexicographic kernel of a game ⋮ On the core and nucleolus of directed acyclic graph games ⋮ A generalization of obligation rules for minimum cost spanning tree problems ⋮ A cooperative location game based on the 1-center location problem ⋮ Path cooperative games ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ An efficient characterization of submodular spanning tree games ⋮ Network strength games: the core and the nucleolus ⋮ Social exchange networks with distant bargaining ⋮ Total balancedness condition for Steiner tree games. ⋮ Traveling salesman games with the Monge property ⋮ Computational complexity in additive hedonic games ⋮ Computing Shapley values in the plane

Cites Work

• Unnamed Item
• Unnamed Item
• On the core of network synthesis games
• Geometric algorithms and combinatorial optimization
• Cores of convex games
• The irreducible Core of a minimum cost spanning tree game
• Minimum cost spanning tree games
• The Relationship Between Convex Games and Minimum Cost Spanning Tree Games: A Case for Permutationally Convex Games
• Computational Complexity of a Cost Allocation Approach to a Fixed Cost Spanning Forest Problem
• Cost allocation for a spanning tree
• On cost allocation for a spanning tree: A game theoretic approach
• Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
• On the Complexity of Cooperative Solution Concepts

This page was built for publication: On the complexity of testing membership in the core of min-cost spanning tree games