G. Bergantiños Cid, L. Lorenzo Picado, S. Lorenzo Freire, J. J. Vidal Puga
Consider a group of agents located at different geographical places that are interested in some resource that can only be provided by a common supplier. Agents can be served directly from the supplier or indirectly through other agents or some public switches. The connection between two agents, an agent and the source, an agent and a switch, or a switch and the source entail some cost. The first problem that we need to solve is how to provide all the agents with the resource with a minimal total cost. This problem is known as the Steiner tree problem and it has been proved to be NP-hard. So heuristics need to be applied. Assume that using some software, we obtain a tree that connects all the agents with the source that might use some public switches. This kind of problems generalize the classical minimum cost spanning tree problem where no public nodes are allowed. Given this situation, we address the problem of allocating the total cost among the agents in a stable way.
Palabras clave: OR games,minimum cost spanning tree problems, Steiner trees, core selection
Programado
JC2 Teoría de juegos 1
19 de abril de 2012 12:00
Sala Bruselas
