文献

J-GLOBAL ID：201802269236038323   整理番号：18A0263501

協力マッチングゲームの効率的安定化【Powered by NICT】

Efficient stabilization of cooperative matching games

著者 (5件)： Ito Takehiro (Tohoku University, Japan) ,  Kakimura Naonori (University of Tokyo, Japan) ,  Kamiyama Naoyuki (Kyushu University/JST, PRESTO, Japan) ,  Kobayashi Yusuke (University of Tsukuba, Japan) ,  Okamoto Yoshio (University of Electro-Communications, Japan)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 677  ページ： 69-82  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 協調マッチングゲームは部分的にネットワーキング環境における交渉解との関連のために多くの関心を集めている。しかし,研究下でのネットワークは安定な交渉結果を生じさせることを保証されているわけではない。この問題に対処するために,安定した結果,改質は可能な限り小さくなければならないがネットワークをもたらすことを,安定化と呼ばれる,改質過程を考察した。問題であるグラフの組合せ最適化問題に向けた。エッジ除去による安定化はNP困難であることが示された。これに反して,本論文では,著者らは,すなわち,端部,頂点除去と頂点の追加,安定化の他の可能な方法は,すべての多項式時間可解であることを示した。ネットワーク安定化問題の自然四変異体の完全な複雑性-理論的分類を得た。加重変異体を研究し,エッジ添加とバーテックス除去のための変異体はNP困難であることを証明した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 組合せ最適化問題 ,  NP困難 ,  グラフ ,  *マッチング ,  折衝 ,  ネットワーク
準シソーラス用語： 加重 ,  複雑性 ,  多項式時間 ,  ネットワーキング , 【Automatic Indexing@JST】

著者キーワード (6件)： 協力ゲーム ,  コア ,  Gallai-Edmonds分解 ,  マッチング ,  ネットワーク交渉 ,  溶液概念

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 協力 ,  マッチング ,  ゲーム ,  安定化