| 講演名 | 2017-03-07 探索者数最適なオンライングラフ探索アルゴリズム 八神 貴裕(九大), 山内 由紀子(九大), 来嶋 秀治(九大), 山下 雅史(九大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフ探索問題は、グラフ内を逃げ回る侵入者を複数の探索者によって発見する問題である．辺探索ゲームはオフラインかつ集中型のグラフ探索問題で，グラフ上のペブルゲームでモデル化される．このモデルでグラフGの探索に十分な最小の石の個数をes(G)で表す．オンラインかつ分散型のグラフ探索問題も研究が進んでおり，そこでは，問題はモバイルエージェントモデルを用いて定式化している．本稿では，新しいオンラインかつ分散型のモデルを提案する．本モデルでは，ポート番号，ホームベース，ホワイトボードといった，モバイルネットワークに用いられる人工的な機構を一切仮定しない．本モデルの下で，探索者数に関して最適，つまりes(G)人の探索者でGを探索するオンライン探索アルゴリズムを提案する． |
| 抄録(英) | The graph search problem is the problem of searching for a mobile evader in a graph by mobile searchers.The edge search game is an offline and centralized version of this problem, and is modeled by a pebble game.Let es(G) be the minimum number of pebbles sufficient to search a graph G in this model.An online and distributed version of this problem has been investigated, and the problem is formalized by mobile agent model.We propose a new online and distributed setting.This setting does not assume artificial tools such that the port number, homebase or whiteboard in the graph.We propose an online search algorithm for es(G) searchers, i.e., this is optimal in terms of the number of searchers. |
| キーワード(和) | グラフ探索問題 / オンラインアルゴリズム / 分散アルゴリズム / 非同期探索者 / 匿名グラフ |
| キーワード(英) | graph search problem / online algorithm / distributed algorithm / asynchronous searchers / anonymous graph |
| 資料番号 | COMP2016-54 |
| 発行日 | 2017-02-28 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2017/3/7(から1日開催) |
| 開催地（和） | 南山大学 |
| 開催地（英） | Nanzan University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 伊藤 大雄(電通大) |
| 委員長氏名（英） | Hiroo Itoh(Univ. of Electro-Comm.) |
| 副委員長氏名（和） | 宇野 裕之(阪府大) |
| 副委員長氏名（英） | Yuushi Uno(Osaka Pref. Univ.) |
| 幹事氏名（和） | 脊戸 和寿(成蹊大) / 斎藤 寿樹(神戸大) |
| 幹事氏名（英） | Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kobe Univ.) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 探索者数最適なオンライングラフ探索アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Optimal Online Graph Search Algorithm in terms of the Number of Searchers |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ探索問題 / graph search problem |
| キーワード(2)（和/英） | オンラインアルゴリズム / online algorithm |
| キーワード(3)（和/英） | 分散アルゴリズム / distributed algorithm |
| キーワード(4)（和/英） | 非同期探索者 / asynchronous searchers |
| キーワード(5)（和/英） | 匿名グラフ / anonymous graph |
| 第 1 著者 氏名（和/英） | 八神 貴裕 / Takahiro Yakami |
| 第 1 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 第 2 著者 氏名（和/英） | 山内 由紀子 / Yukiko Yamauchi |
| 第 2 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 第 3 著者 氏名（和/英） | 来嶋 秀治 / Shuji Kijima |
| 第 3 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 第 4 著者 氏名（和/英） | 山下 雅史 / Masafumi Yamashita |
| 第 4 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 発表年月日 | 2017-03-07 |
| 資料番号 | COMP2016-54 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | COMP-503 |
| ページ範囲 | pp.21-28(COMP), |
| ページ数 | 8 |
| 発行日 | 2017-02-28 (COMP) |