论文标题
在1间连接的图中聚集
Gathering in 1-Interval Connected Graphs
论文作者
论文摘要
我们研究了在动态图中收集$ k \ geq 2 $代理（或多代理集合）的问题，这些图形可能会在每个同步回合中都会发生变化，但始终保持连接（$ 1 $ -Interval连接性）[KLO10]。代理是相同的，没有明确的通信功能，最初位于图的不同节点上。问题是要使代理在相同的节点上收集，而不是预先修复。我们首先表明如果图具有周期，则无法解决问题。鉴于此，我们研究了这个问题的轻松版本，称为弱聚会。我们表明，只有在单行图中，弱聚会才能解决，并且我们为此问题提供了确定性算法，该算法以多项式数量的回合数量运行。
We examine the problem of gathering $k \geq 2$ agents (or multi-agent rendezvous) in dynamic graphs which may change in every synchronous round but remain always connected ($1$-interval connectivity) [KLO10]. The agents are identical and without explicit communication capabilities, and are initially positioned at different nodes of the graph. The problem is for the agents to gather at the same node, not fixed in advance. We first show that the problem becomes impossible to solve if the graph has a cycle. In light of this, we study a relaxed version of this problem, called weak gathering. We show that only in unicyclic graphs weak gathering is solvable, and we provide a deterministic algorithm for this problem that runs in polynomial number of rounds.
