| 講演名 | 2018-12-12 モバイルエージェントによる自己安定グラフ探索 原 悠樹(阪大), 首藤 裕一(阪大), 角川 裕次(阪大), 増澤 利光(阪大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ロータールーターはモバイルエージェントによるグラフの永続探索を実現する自己安定アルゴリズムである．すなわち，どのような初期状況から実行を開始しても，いずれモバイルエージェントはあるオイラー閉路に沿った巡回を繰り返す．本稿は各ノードごとにエージェントが訪問したポート番号の順序を記憶するようにロータールーターを拡張することによって，グラフの辺が削除された際に，新たなオイラー閉路を再構築するまでの時間の改善する手法を提案し，その性能の評価を行う． |
| 抄録(英) | The rotor-router is a self-stabilizing algorithm for graph exploration by a mobile agent, that is, it eventually allows, when started from an arbitrary configuration, an agent to repeatedly traverse a graph along a Euler tour. We present a method to improve the time for reconstructing a new Euler tour when an edge is removed from a graph by recording at each node the cyclic order of the ports the agent coming through, and evaluate its performance. |
| キーワード(和) | グラフ探索, / ロータールータ / モバイルエージェント / 自己安定 / オイラー閉路 |
| キーワード(英) | graph exploration / rotor-router / mobile agent / self-stabilization / Euler tour |
| 資料番号 | COMP2018-39 |
| 発行日 | 2018-12-05 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2018/12/12(から1日開催) |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | モバイルエージェントによる自己安定グラフ探索 |
| サブタイトル（和） | |
| タイトル（英） | Self-stabilizing exploration of a graph by a mobile agent |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ探索, / graph exploration |
| キーワード(2)（和/英） | ロータールータ / rotor-router |
| キーワード(3)（和/英） | モバイルエージェント / mobile agent |
| キーワード(4)（和/英） | 自己安定 / self-stabilization |
| キーワード(5)（和/英） | オイラー閉路 / Euler tour |
| 第 1 著者 氏名（和/英） | 原 悠樹 / Yuki Hara |
| 第 1 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 2 著者 氏名（和/英） | 首藤 裕一 / Yuichi Sudo |
| 第 2 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 3 著者 氏名（和/英） | 角川 裕次 / Hirotsugu Kakugawa |
| 第 3 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 4 著者 氏名（和/英） | 増澤 利光 / Toshimitsu Masuzawa |
| 第 4 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 発表年月日 | 2018-12-12 |
| 資料番号 | COMP2018-39 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | COMP-356 |
| ページ範囲 | pp.47-54(COMP), |
| ページ数 | 8 |
| 発行日 | 2018-12-05 (COMP) |