| アイテムタイプ |
共通アイテムタイプ(1) |
| 公開日 |
2025-05-13 |
| タイトル |
|
|
タイトル |
Near-Linear Time Dispersion of Mobile Agents |
|
言語 |
en |
| 著者 |
Sudo, Yuichi
柴田, 将拡
Nakamura, Junya
Kim, Yonghwan
Masuzawa, Toshimitsu
|
| 著作権関連情報 |
|
|
権利情報Resource |
https://creativecommons.org/licenses/by/4.0/ |
|
権利情報 |
Copyright (c) Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa; licensed under Creative Commons License CC-BY 4.0 |
|
言語 |
en |
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
Consider that there are k ≤ n agents in a simple, connected, and undirected graph G = (V,E) with n nodes and m edges. The goal of the dispersion problem is to move these k agents to mutually distinct nodes. Agents can communicate only when they are at the same node, and no other communication means, such as whiteboards, are available. We assume that the agents operate synchronously. We consider two scenarios: when all agents are initially located at a single node (rooted setting) and when they are initially distributed over one or more nodes (general setting). Kshemkalyani and Sharma presented a dispersion algorithm for the general setting, which uses O(m_k) time and log(k + Δ) bits of memory per agent [OPODIS 2021], where m_k is the maximum number of edges in any induced subgraph of G with k nodes, and Δ is the maximum degree of G. This algorithm is currently the fastest in the literature, as no o(m_k)-time algorithm has been discovered, even for the rooted setting. In this paper, we present significantly faster algorithms for both the rooted and the general settings. First, we present an algorithm for the rooted setting that solves the dispersion problem in O(klog min(k,Δ)) = O(klog k) time using O(log (k+Δ)) bits of memory per agent. Next, we propose an algorithm for the general setting that achieves dispersion in O(k log k ⋅ log min(k,Δ)) = O(k log² k) time using O(log (k+Δ)) bits. Finally, for the rooted setting, we give a time-optimal (i.e., O(k)-time) algorithm with O(Δ+log k) bits of space per agent. All algorithms presented in this paper work only in the synchronous setting, while several algorithms in the literature, including the one given by Kshemkalyani and Sharma at OPODIS 2021, work in the asynchronous setting. |
|
言語 |
en |
| 備考 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
38th International Symposium on Distributed Computing (DISC 2024), October 28 - November 1, 2024, Madrid, Spain |
|
言語 |
en |
| 書誌情報 |
en : Leibniz International Proceedings in Informatics
巻 319,
p. 38,
発行日 2024-10-24
|
| 出版社 |
|
|
出版者 |
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 出版タイプ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.4230/LIPIcs.DISC.2024.38 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1868-8969 |
| 会議記述 |
|
|
|
会議名 |
38th International Symposium on Distributed Computing (DISC 2024) |
|
|
言語 |
en |
|
回次 |
38 |
|
|
開始年 |
2024 |
|
|
開始月 |
10 |
|
|
開始日 |
28 |
|
|
終了年 |
2024 |
|
|
終了月 |
11 |
|
|
終了日 |
01 |
|
|
開催地 |
Madrid |
|
|
言語 |
en |
|
開催国 |
ESP |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/100001003_ja.html |
| 論文ID（連携） |
|
|
値 |
10448839 |
| 連携ID |
|
|
値 |
14480 |
10448839.pdf (926.8 KB)
