| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2017-03-07 14:50 探索者数最適なオンライングラフ探索アルゴリズム ○八神貴裕・山内由紀子・来嶋秀治・山下雅史（九大）  COMP2016-54 |
|
| 抄録 | （和） | グラフ探索問題は、グラフ内を逃げ回る侵入者を複数の探索者によって発見する問題である．辺探索ゲームはオフラインかつ集中型のグラフ探索問題で，グラフ上のペブルゲームでモデル化される．このモデルでグラフ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 / / / | |
| 文献情報 | 信学技報, vol. 116, no. 503, COMP2016-54, pp. 21-28, 2017年3月. | |
| 資料番号 | COMP2016-54 | |
| 発行日 | 2017-02-28 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2016-54 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2017-03-07 - 2017-03-07 |
| 開催地（和） | 南山大学 |
| 開催地（英） | Nanzan University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2017-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 探索者数最適なオンライングラフ探索アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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.) |
| 講演者 | 第1著者 |
| 発表日時 | 2017-03-07 14:50:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2016-54 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.503 |
| ページ範囲 | pp.21-28 |
| ページ数 | 8 |
| 発行日 | 2017-02-28 (COMP) |
[研究会発表申込システムのトップページに戻る]