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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: PhuocHoang Le, Tri-Dung Nguyen, Tolga Bektaş
Formato: article
Lenguaje:EN
Publicado: Elsevier 2016
Materias:
Acceso en línea:https://doaj.org/article/d28e207ef285494bbd207cfa51dabe35
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
Descripción
Sumario: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.