REDUCTION OF ULTRAMETRIC MINIMUM COST SPANNING TREE GAMES TO COST ALLOCATION GAMES ON ROOTED TREES
REDUCTION OF ULTRAMETRIC MINIMUM COST SPANNING TREE GAMES TO COST ALLOCATION GAMES ON ROOTED TREES
复制标题
将超度量最小成本生成树博弈简化为有根树上的成本分配博弈
DOI：
10.15807/jorsj.53.62
复制
发表时间：
2010
影响因子：
--
通讯作者：
Shinji Kato
中科院分区：
文献类型：
--
作者：
Kazutoshi Ando;Shinji Kato
如果基础网络的边缘上的成本功能是超级实数，则最低成本跨越树木游戏被称为超级量。我们表明，每个超级最低成本跨越树游戏的成本都将减少到根生树上的成本分配游戏。因此，存在O（n 2）时间算法，用于计算Shapley价值，核仁和超级最低成本跨越树游戏的平均分配，其中N是玩家的数量。
A minimum cost spanning tree game is called ultrametric if the cost function on the edges of the underlying network is an ultrametric. We show that every ultrametric minimum cost spanning tree game is reduced to a cost allocation game on a rooted tree. It follows that there exist O(n 2 ) time algorithms for computing the Shapley value, the nucleolus and the egalitarian allocation of the ultrametric minimum cost spanning tree games, where n is the number of players.
影响因子：
6.1
作者：
DUTTA, B;RAY, D
通讯作者：
RAY, D