講演抄録/キーワード |
講演名 |
2018-09-18 14:55
構造的パラメータを用いた頂点Kaylesの解析 ○小林靖明(京大) COMP2018-16 |
抄録 |
(和) |
頂点Kaylesはグラフ上の2人プレイヤーの不偏な組合せゲームのひとつである.与えられたグラフにおいて,各プレイヤーは交互にすでに選択された頂点と隣接しないように頂点を選択していき,頂点を選択できなくなったプレイヤーが敗北する.このゲームにおいて,先手に必勝戦略があるかどうかを判定する問題はPSPACE完全であることが知られている.この問題に対するアルゴリズム的研究はいくつか行われてきており,本研究では固定パラメータ容易性の観点で解析を行う.具体的には,与えられたグラフの頂点被覆数またはモジュラー幅をパラメータとしたとき,頂点Kaylesは固定パラメータ容易であることを示す. |
(英) |
|
キーワード |
(和) |
頂点Kayles / 固定パラメータ容易 / 構造的パラメータ化 / 組合せゲーム理論 / / / / |
(英) |
/ / / / / / / |
文献情報 |
信学技報, vol. 118, no. 216, COMP2018-16, pp. 49-53, 2018年9月. |
資料番号 |
COMP2018-16 |
発行日 |
2018-09-11 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2018-16 |