文献

J-GLOBAL ID：201802261308498699   整理番号：18A0260823

サブドミナントサイクル完全コスト関数と周期完全解のための効率的なアルゴリズム【Powered by NICT】

Efficient algorithms for subdominant cycle-complete cost functions and cycle-complete solutions

著者 (3件)： Ando Kazutoshi (Faculty of Engineering, Shizuoka University, Hamamatsu, Shizuoka 432-8561, Japan) ,  Inagaki Ryosuke (Graduate School of Integrated Science and Technology, Shizuoka University, Hamamatsu, Shizuoka 432-8561, Japan) ,  Shoji Kazuya (Graduate School of Integrated Science and Technology, Shizuoka University, Hamamatsu, Shizuoka 432-8561, Japan)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 225  ページ： 1-10  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Trudeau(2012)によって導入された周期完全解は最小コストスパンニング木ゲームの解概念であると費用関数の変化にコア選択と感度のような望ましい特性を有していることが証明された。サイクル完全解は,与えられた費用関数のサブドミナントサイクル完全なコスト関数に関連した最小コストスパンニング木ゲームのShapley値として定義される。本研究では,著者らはサブドミナントサイクル完全なコスト関数を特性化し,そのような関数を計算するためのO(n2logn)時間アルゴリズムを提供し,nは選手の数であった。このアルゴリズムはO(n2logn)時間限界を持つ最小コストスパンニング木ゲームのサイクル完全解を計算するための新しいアルゴリズムを導いた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *アルゴリズム ,  キャラクタリゼーション ,  スパンニング木 ,  ゲーム ,  *費用関数
準シソーラス用語： 運動選手 ,  Shapley値 , 【Automatic Indexing@JST】

著者キーワード (5件)： 協力ゲーム ,  最小スパンニング木 ,  Shapley値 ,  計算の複雑さ ,  劣モジュラ関数

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

タイトルに関連する用語 (3件)： コスト関数 ,  周期 ,  アルゴリズム