Abstract | ||
---|---|---|
A minimum cost shortest-path tree is a tree that connects the source with every node of the network by a shortest path such that the sum of the cost (as a proxy for length) of all arcs is minimum.In this paper, we adapt the algorithm of Hansen and Zheng (Discrete Appl. Math. 65:275–284, ) to the case of acyclic directed graphs to find a minimum cost shortest-path tree in order to be applied to the cost allocation problem associated with a cooperative minimum cost shortest-path tree game. In addition, we analyze a non-cooperative game based on the connection problem that arises in the above situation. We prove that the cost allocation given by an ‘à la’ Bird rule provides a core solution in the former game and that the strategies that induce those payoffs in the latter game are Nash equilibrium. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/s10479-011-1043-8 | Annals OR |
Keywords | Field | DocType |
Operations research games,Core solution,Nash equilibrium | Discrete mathematics,Mathematical optimization,Distributed minimum spanning tree,Shortest path problem,Spanning tree,Nash equilibrium,Shortest-path tree,Game tree,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
199 | 1 | 0254-5330 |
Citations | PageRank | References |
2 | 0.40 | 9 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Francisco R. Fernández | 1 | 176 | 18.42 |
Justo Puerto | 2 | 717 | 73.21 |