文献

J-GLOBAL ID：201002227878393977   整理番号：10A0786134

超計量最小コストスパンニング木ゲームの根付き木上のコスト割付ゲームへの簡略化

REDUCTION OF ULTRAMETRIC MINIMUM COST SPANNING TREE GAMES TO COST ALLOCATION GAMES ON ROOTED TREES

著者 (2件)： ANDO Kazutoshi (Shizuoka Univ.) ,  KATO Shinji (Shizuoka Univ.)
資料名： Journal of the Operations Research Society of Japan  (Journal of the Operations Research Society of Japan)
巻： 53  号： 1  ページ： 62-68  発行年： 2010年03月 
JST資料番号： G0402A  ISSN： 0453-4514  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 最小コストスパンニング木ゲームは,内在するネットワークの辺上の費用関数が超計量な場合,超計量と呼ばれる。すべての超計量最小コストスパンニング木ゲームが,根付き木上のコスト割付ゲームに簡略化されることを示した。続けて,Shapley値を計算するためのO(n²)時間アルゴリズム-超計量最小コストスパンニング木ゲームの核小体・平等割付,そこではnはプレーヤ数を表わす-が存在することを記述した。(翻訳著者抄録)

シソーラス用語： *スパンニング木 ,  計量 ,  *ゲーム理論 ,  費用関数 ,  計算機アルゴリズム ,  核小体 ,  *組合せ最適化問題 ,  資源割付 ,  完全グラフ ,  協力ゲーム ,  定理証明 ,  最小化問題 ,  コスト最小化 ,  *理論

分類 (1件)： ゲーム理論  (KA03060T)

引用文献 (19件)：

• AARTS, H. The irreducible core of a minimum cost spanning tree game. Mathematical Methods of Operations Research. 1993, 38, 163-174
• BIRD, C. G. On cost allocation for a spanning tree. A game theoretic approach. Networks. 1976, 6, 335-350
• DUTTA, B. A concept of egalitarianism under participation constraints. Econometrica. 1989, 57, 615-635
• FAIGLE, U. On the complexity of testing membership in the core of min-cost spanning tree games. International Journal of Game Theory. 1997, 26, 361-366
• FAIGLE, U. Computing the nucleolus of min-cost spanning tree games is NP-hard. International Journal of Game Theory. 1998, 27, 443-450

タイトルに関連する用語 (6件)： 計量 ,  スパンニング木 ,  ゲーム ,  根付き木 ,  割付 ,  簡略化