Partial gathering of mobile agents in dynamic rings

In this paper, we consider the partial gathering problem of mobile agents in synchronous dynamic bidirectional ring networks. 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. When k ≥ 2 g , 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, the partial gathering problem has been considered in static graphs. In this paper, we start considering partial gathering in dynamic graphs. As a first step, we consider this problem in 1-interval connected rings, that is, one of the links in a ring may be missing at each time step. In such networks, focusing on the relationship between the values of k and g , we fully characterize the solvability of the partial gathering problem and analyze the move complexity of the proposed algorithms when the problem can be solved. First, we show that the g -partial gathering problem is unsolvable when k ≤ 2 g . Second, we show that the problem can be solved with O ( n log g ) time and the total number of O ( gn log g ) moves when 2 g + 1 ≤ k ≤ 3 g − 2 . Third, we show that the problem can be solved with O ( n ) time and the total number of O ( kn ) moves when 3 g − 1 ≤ k ≤ 8 g − 4 . Notice that since k = O ( g ) holds when 3 g − 1 ≤ k ≤ 8 g − 4 , the move complexity O ( kn ) in this case can be represented also as O ( gn ). Finally, we show that the problem can be solved with O ( n ) time and the total number of O ( gn ) moves when k ≥ 8 g − 3 . These results mean that the partial gathering problem can be solved also in dynamic rings when k ≥ 2 g + 1 . In addition, agents require a total number of Ω( gn ) (resp., Ω( kn )) moves to solve the partial (resp., total) gathering problem. Thus, when k ≥ 3 g − 1 , agents 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.