Partial Gathering of Mobile Agents in Arbitrary Networks
-
- SHIBATA Masahiro
- Department of Computer Science and Electronics, Kyushu Institute of Technology
-
- NAKAMURA Daisuke
- Graduate School of Information Science, NAIST
-
- OOSHITA Fukuhito
- Graduate School of Information Science and Technology, Osaka University
-
- KAKUGAWA Hirotsugu
- Graduate School of Information Science, NAIST
-
- MASUZAWA Toshimitsu
- Graduate School of Information Science, NAIST
この論文をさがす
抄録
<p>In this paper, we consider the partial gathering problem of mobile agents in arbitrary networks. The partial gathering problem is a generalization of the (well-investigated) total 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 no stronger than that for the total gathering problem, and thus, we clarify the difference on the move complexity between them. First, we show that agents require Ω(gn+m) total moves to solve the partial gathering problem, where n is the number of nodes and m is the number of communication links. Next, we propose a deterministic algorithm to solve the partial gathering problem in O(gn+m) total moves, which is asymptotically optimal in terms of total moves. Note that, it is known that agents require Ω(kn+m) total moves to solve the total gathering problem in arbitrary networks, where k is the number of agents. Thus, our result shows that the partial gathering problem is solvable with strictly fewer total moves compared to the total gathering problem in arbitrary networks.</p>
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E102.D (3), 444-453, 2019-03-01
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390564238078861440
-
- NII論文ID
- 130007605745
-
- NII書誌ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 10228/00007313
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可