论文标题
简短公告：在动态植根的树中的广播时间是线性的
Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear
论文作者
论文摘要
我们使用$ n $流程研究动态网络上的广播问题。这些过程沿任意生根的树以同步回合进行通信。树木的顺序是由对手给出的，其目标是最大化回合的数量，直到至少一个过程达到所有其他过程。先前的研究显示了一个$ \ lceil {\ frac {3n-1} {2}}} \ rceil-2 $下限和$ O（n \ log \ log n）$上限。我们显示了此问题的第一个线性上限，即$ \ lceil {（1 + \ sqrt 2）n-1} \ rceil \ rceil \大约2.4n $。我们的结果是根据对网络邻近矩阵的演变的详细分析。
We study the broadcast problem on dynamic networks with $n$ processes. The processes communicate in synchronous rounds along an arbitrary rooted tree. The sequence of trees is given by an adversary whose goal is to maximize the number of rounds until at least one process reaches all other processes. Previous research has shown a $\lceil{\frac{3n-1}{2}}\rceil-2$ lower bound and an $O(n\log\log n)$ upper bound. We show the first linear upper bound for this problem, namely $\lceil{(1 + \sqrt 2) n-1}\rceil \approx 2.4n$. Our result follows from a detailed analysis of the evolution of the adjacency matrix of the network over time.
