For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Partial Gathering of Mobile Agents in Arbitrary Networks
Masahiro SHIBATA Daisuke NAKAMURA Fukuhito OOSHITA Hirotsugu KAKUGAWA Toshimitsu MASUZAWA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2019/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
distributed system, mobile agent, gathering problem, partial gathering problem,
Full Text: PDF(769.9KB)
>>Buy this Article
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.