WEKO3
アイテム
Partial gathering of mobile agents in dynamic rings
http://hdl.handle.net/10228/00008996
http://hdl.handle.net/10228/000089968740f8ff-8e25-4a68-8417-f4a2c7f503b3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
RECN_2021-39.pdf (334.2 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-11-09 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Partial gathering of mobile agents in dynamic rings | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
柴田, 将拡
× 柴田, 将拡
WEKO
25091
× Sudo, Yuichi× Nakamura, Junya× Kim, Yonghwan |
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | In this paper, we consider the partial gathering problem of mobile agents in synchronous dynamic bidirectional rings. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all k agents distributed in the network terminate at a non-predetermined single node. The partial gathering problem requires, for a given positive integer g(<k), that agents terminate in a configuration such that either at least g agents or no agent exists at each node. The requirement for the partial gathering problem is strictly weaker than that for the total gathering problem, and thus it is interesting to clarify the difference in the move complexity between them. So far, partial gathering has been considered in static graphs. In this paper, we consider this problem in 1-interval connected rings, that is, one of the links in the ring may be missing at each time step. In such networks, we aim to clarify the solvability of the partial gathering problem and the move complexity, focusing on the relationship between values of k and g. First, we consider the case of 3g≤k≤8g−2. In this case, we show that our algorithm can solve the problem with the total number of O(kn) moves, where n is the number of nodes. Since k=O(g) holds when 3g≤k≤8g−2, the move complexity O(kn) in this case can be represented also as O(gn). Next, we consider the case of k≥8g−3. In this case, we show that our algorithm can also solve the problem and its move complexity is O(gn). These results mean that, when k≥3g, the partial gathering problem can be solved also in dynamic rings. In addition, agents require a total number of Ω(gn) (resp., Ω(kn)) moves to solve the partial (resp., total) gathering problem. Thus, the both proposed algorithms can solve the partial gathering problem with the asymptotically optimal total number of O(gn) moves, which is strictly smaller than that for the total gathering problem. | |||||||||||||
| 言語 | en | |||||||||||||
| 備考 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, November 17-20, 2021, Virtual Conference | |||||||||||||
| 書誌情報 |
en : Lecture Notes in Computer Science 巻 13046, p. 440-455, 発行日 2021-11-09 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | Springer | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1007/978-3-030-91081-5_29 | |||||||||||||
| ISBN | ||||||||||||||
| 識別子タイプ | ISBN | |||||||||||||
| 関連識別子 | 978-3-030-91080-8 | |||||||||||||
| ISBN | ||||||||||||||
| 識別子タイプ | ISBN | |||||||||||||
| 関連識別子 | 978-3-030-91081-5 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0302-9743 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||
| 収録物識別子 | 1611-3349 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2021 Springer Nature Switzerland AG. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-91081-5_29. | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | mobile agent | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | partial gathering problem | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | dynamic ring | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | AM | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 10296 | |||||||||||||
