Move-optimal partial gathering of mobile agents in asynchronous trees
Move-optimal partial gathering of mobile agents in asynchronous trees
复制标题
异步树中移动代理的移动最优部分聚集
DOI：
10.1016/j.tcs.2017.09.016
复制
发表时间：
2018
影响因子：
1.1
通讯作者：
Masuzawa Toshimitsu
中科院分区：
文献类型：
--
作者：
Shibata Masahiro;Ooshita Fukuhito;Kakugawa Hirotsugu;Masuzawa Toshimitsu
本文研究了异步树型网络中移动的代理的部分聚集问题。部分聚集问题是经典聚集问题的推广，它要求所有的代理在同一个节点上相遇。部分聚集问题要求，对于给定的正整数g，每个代理应该移动到一个节点并终止，使得至少g个代理应该在它们终止的每个节点处相遇。部分聚集问题的要求比经典聚集问题的要求要弱，因此，我们澄清了它们之间在移动复杂性上的差异。我们考虑了两种多重性检测模型：弱多重性检测模型和强多重性检测模型。在弱多重性检测模型中，每个代理可以检测当前节点上是否存在另一个代理，但不能计算代理的确切数量。在强多重性检测模型中，每个代理可以计算当前节点上的代理数量。此外，我们考虑了两种令牌模型：非令牌模型和可移动令牌模型。在非令牌模型中，代理不能以任何方式标记节点或边。在可移除令牌模型中，每个代理最初在其初始节点上留下令牌，并且代理可以移除令牌。我们的贡献如下：首先，我们证明了对于非令牌模型，代理需要Ω（k n）总移动来解决部分收集问题，其中n是节点的数量，k是代理的数量。其次，我们考虑弱多重检测和无令牌模型。在该模型中，对于非对称树，通过一个先前的结果代理可以实现部分收集在O（kn）总移动，这是渐近最优的总移动。此外，对于对称树，我们表明，不存在算法来解决部分收集问题。第三，我们考虑了强多重性检测和非令牌模型。在这个模型中，对于任何树，我们提出了一个算法，以实现部分收集在O（k n）总移动，这是渐近最优的总移动。最后，我们考虑了弱多重检测和可移动令牌模型。在这个模型中，我们提出了一个算法，以实现部分收集在O（g n）的总动作。请注意，在这个模型中，代理需要Ω（g n）总移动来解决部分收集问题。因此，第二个算法也是渐近最优的总移动。
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 Ω (k n) 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 (k n) 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 (k n) 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 (g n) total moves. Note that in this model, agents require Ω (g n) total moves to solve the partial gathering problem. Hence, the second proposed algorithm is also asymptotically optimal in terms of total moves.