文献

J-GLOBAL ID：202202227593873327   整理番号：22A0376547

追跡回避ゲームにおけるツールとしてのサブグラフの保護【JST・京大機械翻訳】

Guarding a Subgraph as a Tool in Pursuit-Evasion Games

著者 (2件)： Bokal Drago (Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia) ,  Jerebic Janja (Faculty of Organizational Sciences, University of Maribor, Kranj, Slovenia)
資料名： Discussiones Mathematicae Graph Theory (Web)  (Discussiones Mathematicae Graph Theory (Web))
巻： 42  号： 1  ページ： 123-138  発行年： 2022年 
JST資料番号： U7977A  ISSN： 2083-5892  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 追跡回避ゲームは,コップとローバーが隣接頂点に交互に移動し,ロブベリーが頂点の頂点上のコップステップを入れるならば,グラフに演じるゲームにおけるロバを捕えるのに必要なコップの数を研究する。グラフのこのcop数を解析する一般的なツールはグラフにおける最短経路に沿って移動するコップであり,それにより,この経路に回転するのを防ぐ。著者らは,このアプローチを,ロバーの影を導入することによって一般化し,そこから頂点の最大集合は,保護部分グラフを分割する。この状況において,ローバーは侵入者になり,コップはガードになる。シャドウは多項式時間で計算でき,成功したガードと成功する侵入者の両方を計算するための多項式時間アルゴリズムを意味することを示した。さらに,シャドウ関数がグラフ後退の概念を一般化することを示した。ある場合には,これは与えられた部分グラフへの後退の存在のNP完全問題に対する負の回答の多項式計算可能な認証を意味する。Please refer to the publisher for the copyright holders. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 多項式 ,  *ゲーム ,  *部分グラフ ,  NP完全問題
準シソーラス用語： 多項式時間 ,  多項式時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (2件)： 05C57 ,  05C_60

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： 追跡 ,  回避 ,  ゲーム ,  ツール ,  サブグラフ