文献

J-GLOBAL ID：201202211801333727   整理番号：12A0163821

木状泥棒領域を持つグラフ護衛問題の近似

How to guard a graph against tree movements

著者 (2件)： 坂巻孝昌 (豊橋技科大) ,  藤戸敏弘 (豊橋技科大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 111  号： 360(COMP2011 36-46)  ページ： 33-36  発行年： 2011年12月09日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では,無向グラフ上で警官と泥棒の両プレイヤー間でプレイされる護衛ゲームより派生する最適問題について考察し,泥棒領域が木であればΘ(log n)倍以内で同問題を近似できることを示す。(著者抄録)

シソーラス用語： *無向グラフ ,  *ゲーム ,  *最適化問題 ,  計算機アルゴリズム ,  *近似法
準シソーラス用語： 貪欲法 ,  *護衛ゲーム

分類 (2件)： グラフ理論基礎  (IA02020S) ,  システム最適化手法  (IA02050Z)

タイトルに関連する用語 (4件)： 木 ,  グラフ ,  問題 ,  近似