Generalized minimum spanning tree games

Phuoc Hoang Le (), Tri-Dung Nguyen () and Tolga Bektaş ()
Additional contact information
Phuoc Hoang Le: University of Southampton
Tri-Dung Nguyen: University of Southampton
Tolga Bektaş: University of Southampton

EURO Journal on Computational Optimization, 2016, vol. 4, issue 2, No 4, 167-188

Abstract: Abstract 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.

Keywords: Generalized minimum spanning tree game; Cost allocation; Cooperative games; The core; Stability; 91A12 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-015-0042-y Abstract (text/html)
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:eurjco:v:4:y:2016:i:2:d:10.1007_s13675-015-0042-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-015-0042-y

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().