文献

J-GLOBAL ID：201202292460333413   整理番号：12A1718403

最小コストスパンニング木ゲームのShapley値の計算:#P-困難性及び多項式事例

Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases

著者 (1件)： ANDO Kazutoshi (Shizuoka Univ., Fac. of Engineering, 432-8561, Hamamatsu, JPN)
資料名： Japan Journal of Industrial and Applied Mathematics  (Japan Journal of Industrial and Applied Mathematics)
巻： 29  号： 3  ページ： 385-400  発行年： 2012年10月 
JST資料番号： L5671A  ISSN： 0916-7005  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 筆者らは例えコスト関数が{0,1}-値に制限されていたとしても最小コストスパンニング木ゲームのShapley値の計算が#P-困難である事を示した。#P-完全である非有向グラフの最小2-末端頂点切断の数の計測からの還元によって証明を行なった。また,筆者らはShapley値を多項式時間において計算できる最小コストスパンニング木ゲームを研究した。筆者らはもし与えられたネットワークのコスト関数が木測度の一般化である部分木距離ならば,関連した最小コストスパンニング木ゲームのShapley値をO(n⁴)時間において計算できる事を示した。ここでnは競技者の数とする。Copyright 2012 The JJIAM Publishing Committee and Springer Translated from English into Japanese by JST.

シソーラス用語： グラフ理論 ,  最小値 ,  原価 ,  *スパンニング木 ,  *ゲーム ,  ゲーム理論 ,  計算量 ,  協力ゲーム ,  *Shapley値 ,  理論
準シソーラス用語： コスト ,  協調ゲーム

分類 (2件)： グラフ理論基礎  (IA02020S) ,  ゲーム理論  (KA03060T)

引用文献 (24件)：

• ABOELFOTOH, H. M. Computing 2-terminal reliability for radio-broadcast networks. IEEE Trans. Reliab. 1989, 38, 538-555
• ANDO, K. Reduction of ultrametric minimum cost spanning tree games to cost allocation games on rooted trees. J. Oper. Res. Soc. Jpn. 2010, 53, 62-68
• AZIZ, H. Power indices in spanning tree games. Proceedings of the 5th International Conference on Algorithmic Aspects in Information and Management-AAIM 2009. 2009, 55-67
• BACHER, R. Determinants of matrices related to the Pascal triangle. J. de Theorie des Nombres de Bordeaux. 2002, 14, 19-41
• BERGANTINOS, G. The optimistic TU game in minimum cost spanning tree problems. Int. J. Game Theory. 2007, 36, 223-239

タイトルに関連する用語 (6件)： スパンニング木 ,  ゲーム ,  Shapley値 ,  計算 ,  困難性 ,  多項式