最小数のエージェント群による動的グラフ探索

• Item type: SIG Technical Reports(1)
• 公開日: 2021-04-30
• タイトル: 最小数のエージェント群による動的グラフ探索
• タイトル / 言語: en
• タイトル: Exploration of dynamic graphs by the minimum number of agents
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 法政大学情報科学部
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Computer and Information Sciences; Hosei University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology Osaka University
• 著者名: 飯塚, 俊介; 首藤, 裕一; 泉, 泰介; 増澤, 利光
• 著者名(英): Shunsuke, Iitsuka; Yuichi, Sudo; Taisuke, Izumi; Toshimitsu, Masuzaawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，利用可能な辺が時間とともに変動する動的グラフの探索問題において，グラフ全体が任意の時刻で連結であるという条件の下で，グラフ全体を探索するために必要なエージェント数について検討する．はじめに，同時に高々 ℓ 本の辺が消失する動的グラフに対し，探索に必要なエージェント数が少なくとも ℓ + 1 体であるような動的グラフが存在することを示す．次に，ℓ + 1 体のエージェントが存在するならば，任意の動的グラフを探索可能であることを，実際にアルゴリズムを提案することにより示す．最後に，提案アルゴリズムの探索時間は，動的グラフの頂点数を ????，辺数を ???? としたとき，???? ((8????????)ℓ+1) であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 ℓ−bounded dynamic graphs, where at most ℓ edges can be disappeared at each time, ℓ + 1 agents are necessarily to explore all vertices. Then, we propose the algorithm which achieves the exploration using ℓ + 1 agents. The exploration time of the proposed algorithm is ???? ((8????????)ℓ+1), where ???? is the number of vertices, and ???? is the number of potential edges in dynamic graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-183, 号 8, p. 1-6, 発行日 2021-04-30
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会