文献

J-GLOBAL ID：201902212808519476   整理番号：19A0010735

構造的パラメータを用いた頂点Kaylesの解析

Structural Parameterizations of Node Kayles

著者 (1件)： 小林靖明 (京大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 118  号： 216(COMP2018 9-20)(Web)  ページ： 49-53 (WEB ONLY)  発行年： 2018年09月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 頂点Kaylesはグラフ上の2人プレイヤーの不偏な組合せゲームのひとつである。与えられたグラフにおいて,各プレイヤーは交互にすでに選択された頂点と隣接しないように頂点を選択していき,頂点を選択できなくなったプレイヤーが敗北する。このゲームにおいて,先手に必勝戦略があるかどうかを判定する問題はPSPACE完全であることが知られている。この問題に対するアルゴリズム的研究はいくつか行われてきており,本研究では固定パラメータ容易性の観点で解析を行う。具体的には,与えられたグラフの頂点被覆数またはモジュラー幅をパラメータとしたとき,頂点Kaylesは固定パラメータ容易であることを示す。(著者抄録)

シソーラス用語： *ゲーム理論 ,  計算量 ,  構造パラメータ ,  *無向グラフ

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

引用文献 (11件)：

• K. R. Abrahamson, R. G. Downey, M. R. Fellows, Fixedparameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues, Ann. Pure Appl. Logic 73(3), 235-276, 1995.
• H. L. Bodlaender, Dynamic programming on graphs with bounded treewidth. In Proc. of ICALP 1988. pp. 105-118, 1988.
• H. L. Bodlaender, D. Kratsch, Kayles and nimbers, J. Algorithms 43, 106-119, 2002.
• H. L. Bodlaender, D. Kratsch, S. T. Timmer, Exact algorithms for Kayles, Theoret. Comput. Sci. 562, 165-176, 2015.
• J. H. Conway, On numbers and games, Academic press, London, 1976.

タイトルに関連する用語 (3件)： パラメータ ,  頂点 ,  解析