WEKO3
アイテム
Move-optimal partial gathering of mobile agents in asynchronous trees
http://hdl.handle.net/10228/00007612
http://hdl.handle.net/10228/00007612e3f8eac0-2c85-4b33-b04f-3a15c3ab5190
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
j.tcs.2017.09.016.pdf (1.2 MB)
|
|
| Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2020-02-13 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Move-optimal partial gathering of mobile agents in asynchronous trees | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
柴田, 将拡
× 柴田, 将拡
WEKO
25091
× Ooshita, Fukuhito× Kakugawa, Hirotsugu× Masuzawa, Toshimitsu |
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | In this paper, we consider the partial gathering problem of mobile agents in asynchronous tree networks. The partial gathering problem is a generalization of the classical gathering problem, which requires that all the agents meet at the same node. The partial gathering problem requires, for a given positive integer g, that each agent should move to a node and terminate so that at least g agents should meet at each of the nodes they terminate at. The requirement for the partial gathering problem is weaker than that for the (well-investigated) classical gathering problem, and thus, we clarify the difference on the move complexity between them. We consider two multiplicity detection models: weak multiplicity detection and strong multiplicity detection models. In the weak multiplicity detection model, each agent can detect whether another agent exists at the current node or not but cannot count the exact number of the agents. In the strong multiplicity detection model, each agent can count the number of agents at the current node. In addition, we consider two token models: non-token model and removable token model. In the non-token model, agents cannot mark the nodes or the edges in any way. In the removable-token model, each agent initially leaves a token on its initial node, and agents can remove the tokens. Our contribution is as follows. First, we show that for the non-token model agents require Ω(kn) total moves to solve the partial gathering problem, where n is the number of nodes and k is the number of agents. Second, we consider the weak multiplicity detection and non-token model. In this model, for asymmetric trees, by a previous result agents can achieve the partial gathering in O(kn) total moves, which is asymptotically optimal in terms of total moves. In addition, for symmetric trees we show that there exist no algorithms to solve the partial gathering problem. Third, we consider the strong multiplicity detection and non-token model. In this model, for any trees we propose an algorithm to achieve the partial gathering in O(kn) total moves, which is asymptotically optimal in terms of total moves. At last, we consider the weak multiplicity detection and removable-token model. In this model, we propose an algorithm to achieve the partial gathering in O(gn) total moves. Note that in this model, agents require Ω(gn) total moves to solve the partial gathering problem. Hence, the second proposed algorithm is also asymptotically optimal in terms of total moves. | |||||||||||||
| 書誌情報 |
Theoretical Computer Science 巻 705, p. 9-30, 発行日 2017-09-27 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | Elsevier | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | info:doi/10.1016/j.tcs.2017.09.016 | |||||||||||||
| NCID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AA00862688 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 0304-3975 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2017 The Authors. Published by Elsevier B.V. | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | This is an open access article under the CC BY license | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | http://creativecommons.org/licenses/by/4.0/ | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Distributed system | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Mobile agent | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Gathering problem | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Partial gathering problem | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | VoR | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 研究者情報 | ||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/100001003_ja.html | |||||||||||||
| 論文ID（連携） | ||||||||||||||
| 値 | 10309739 | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 8118 | |||||||||||||
| 情報源 | ||||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.tcs.2017.09.016 | |||||||||||||
| 関連名称 | https://doi.org/10.1016/j.tcs.2017.09.016 | |||||||||||||
