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:	91A12 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/d28e207ef285494bbd207cfa51dabe35
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:d28e207ef285494bbd207cfa51dabe35
record_format	dspace
spelling	oai:doaj.org-article:d28e207ef285494bbd207cfa51dabe352021-12-02T05:00:51ZGeneralized minimum spanning tree games2192-440610.1007/s13675-015-0042-yhttps://doaj.org/article/d28e207ef285494bbd207cfa51dabe352016-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000605https://doaj.org/toc/2192-4406The 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.PhuocHoang LeTri-Dung NguyenTolga BektaşElsevierarticle91A12Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 4, Iss 2, Pp 167-188 (2016)
institution	DOAJ
collection	DOAJ
language	EN
topic	91A12 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	91A12 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 PhuocHoang Le Tri-Dung Nguyen Tolga Bektaş Generalized minimum spanning tree games
description	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.
format	article
author	PhuocHoang Le Tri-Dung Nguyen Tolga Bektaş
author_facet	PhuocHoang Le Tri-Dung Nguyen Tolga Bektaş
author_sort	PhuocHoang Le
title	Generalized minimum spanning tree games
title_short	Generalized minimum spanning tree games
title_full	Generalized minimum spanning tree games
title_fullStr	Generalized minimum spanning tree games
title_full_unstemmed	Generalized minimum spanning tree games
title_sort	generalized minimum spanning tree games
publisher	Elsevier
publishDate	2016
url	https://doaj.org/article/d28e207ef285494bbd207cfa51dabe35
work_keys_str_mv	AT phuochoangle generalizedminimumspanningtreegames AT tridungnguyen generalizedminimumspanningtreegames AT tolgabektas generalizedminimumspanningtreegames
_version_	1718400856830771200

Generalized minimum spanning tree games

Ejemplares similares