文献

J-GLOBAL ID：201702243068920216   整理番号：17A1500842

最短接続ゲーム【Powered by NICT】

The shortest connection game

著者 (3件)： Darmann Andreas (Institute of Public Economics, University of Graz, Universitaetsstr. 15, 8010 Graz, Austria) ,  Pferschy Ulrich (Department of Statistics and Operations Research, University of Graz, Universitaetsstr. 15, 8010 Graz, Austria) ,  Schauer Joachim (Department of Mathematics, University of Klagenfurt, Universitaetsstr. 65-67, 9020 Klagenfurt, Austria)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 231  ページ： 139-154  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最短接続ゲーム,エッジコストを持つ有向グラフ上で行われる二人ゲームを導入した。選手が始まる二指定された頂点を考慮すると,選手は現在に位置している頂点からエッジを順番に選ぶとを示した。このようにして,選手の各々はその各出発頂点に起因する経路を形成する。ゲームは二経路が出会うとすぐに終了,すなわち,選手の間の関係を確立した。各プレーヤはその選択エッジのコストを備えていなければならない,それ自身の全コストを最小化することを目的としている。本研究では,最短接続ゲームの計算量を解析した。負側では,最短接続ゲームは2つに分かれ,非環式とサボテングラフとしてこのような制限されたグラフクラスでも計算量的に困難であることが分かった。正側では,ゲームは単純経路に限定された場合,サボテングラフのための多項式時間アルゴリズムを与えることができる。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 二人ゲーム ,  *ゲーム ,  計算量 ,  有向グラフ
準シソーラス用語： 多項式時間アルゴリズム ,  プレイヤ , 【Automatic Indexing@JST】

著者キーワード (4件)： 最短路問題 ,  ゲーム理論 ,  計算の複雑さ ,  サボテングラフ

分類 (2件)： 計算理論  (JB02000A) ,  ゲーム理論  (KA03060T)

タイトルに関連する用語 (1件)： ゲーム