Generalized minimum spanning tree games

The minimum-cost spanning tree game is a special class of cooperative games defined on a graph with a set of vertices and a set of edges, where each player owns a vertex. Solutions of the game represent ways to distribute the total cost of a minimum-cost spanning tree among all the players. When the...

Full description

Saved in:
Bibliographic Details
Published in:EURO journal on computational optimization 2016-05, Vol.4 (2), p.167-188
Main Authors: Le, PhuocHoang, Nguyen, Tri-Dung, Bektaş, Tolga
Format: Article
Language:English
Subjects:
91A12
Algorithms
Business and Management
Communication
Cooperative games
Cost allocation
Game theory
Generalized minimum spanning tree game
Graph theory
Joint ventures
Linear programming
Management Science
Mathematical analysis
Network management systems
Operations Management
Operations Research
Operations Research/Decision Theory
Optimization
Original Paper
Stability
Studies
The core
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The minimum-cost spanning tree game is a special class of cooperative games defined on a graph with a set of vertices and a set of edges, where each player owns a vertex. Solutions of the game represent ways to distribute the total cost of a minimum-cost spanning tree among all the players. When the graph is partitioned into clusters, the generalized minimum spanning tree problem is to determine a minimum-cost tree including exactly one vertex from each cluster. This paper introduces the generalized minimum spanning tree game and studies some properties of this game. The paper also describes a constraint generation algorithm to calculate a stable payoff distribution and presents computational results obtained using the proposed algorithm.
ISSN:2192-4406
2192-4414
DOI:10.1007/s13675-015-0042-y