| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-05-07 16:40 最小数のエージェント群による動的グラフ探索 ○飯塚俊介（阪大）・首藤裕一（法政大）・泉 泰介・増澤利光（阪大）  COMP2021-3 |
|
| 抄録 | （和） | 本稿では，利用可能な辺が時間とともに変動する動的グラフの探索問題において，グラフ全体が任意の時刻で連結であるという条件の下で，グラフ全体を探索するために必要なエージェント数について検討する． はじめに，同時に高々$ell$本の辺が消失する動的グラフに対し，探索に必要なエージェント数が少なくとも$ell+1$体であるような動的グラフが存在することを示す．次に，$ell+1$体のエージェントが存在するならば，任意の動的グラフを探索可能であることを，実際にアルゴリズムを提案することにより示す．最後に，提案アルゴリズムの探索時間は，動的グラフの頂点数を$n$,辺数を$m$としたとき，$O((8mn)^{ell+1})$であることを示す． |
| （英） | We consider the collaborative exploration of dynamic graphs by multiple agents, where dynamic graphs are defined as the ones whose edge set changes over (discrete) time, but the snapshot at each time is guaranteed to be connected. Our study focuses on the necessary and sufficient condition for the number of agents to attain the collaborative exploration in arbitrary dynamic graphs. First, we prove that in $ell-$bounded dynamic graphs, where at most $ell$ edges can be disappeared at each time, $ell+1$ agents are necessarily to explore all vertices. Then, we propose the algorithm which achieves the exploration using $ell+1$ agents. The exploration time of the proposed algorithm is $O((8mn)^{ell+1})$, where $n$ is the number of vertices, and $m$ is the number of potential edges in dynamic graphs. |
|
| キーワード | （和） | モバイルエージェント / 動的グラフ探索 / ロータールータ / 分散アルゴリズム / / / / |
| （英） | mobile agent / exploration of dynamic graph / Rotor-Router / distributed algorithm / / / / | |
| 文献情報 | 信学技報, vol. 121, no. 11, COMP2021-3, pp. 17-22, 2021年5月. | |
| 資料番号 | COMP2021-3 | |
| 発行日 | 2021-04-30 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2021-3 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2021-05-07 - 2021-05-08 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2021-05-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 最小数のエージェント群による動的グラフ探索 |
| サブタイトル（和） | |
| タイトル（英） | Exploration of dynamic graphs by the minimum number of agents |
| サブタイトル（英） | |
| キーワード(1)（和/英） | モバイルエージェント / mobile agent |
| キーワード(2)（和/英） | 動的グラフ探索 / exploration of dynamic graph |
| キーワード(3)（和/英） | ロータールータ / Rotor-Router |
| キーワード(4)（和/英） | 分散アルゴリズム / distributed algorithm |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 飯塚 俊介 / Shunsuke Iitsuka / イイツカ シュンスケ |
| 第1著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 首藤 裕一 / Yuichi Sudo / スドウ ユウイチ |
| 第2著者 所属（和/英） | 法政大学 (略称： 法政大) Hosei University (略称： Hosei Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 泉 泰介 / Taisuke Izumi / イズミ タイスケ |
| 第3著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 増澤 利光 / Toshimitsu Masuzawa / マスザワ トシミツ |
| 第4著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-05-07 16:40:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2021-3 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.11 |
| ページ範囲 | pp.17-22 |
| ページ数 | 6 |
| 発行日 | 2021-04-30 (COMP) |
[研究会発表申込システムのトップページに戻る]