论文标题
在路径和周期上广播
Broadcasting on Paths and Cycles
论文作者
论文摘要
考虑以下广播过程在连接的图$ g =（v，e）$上运行。假设$ k \ ge 2 $代理商从从$ v $统一而独立地随机选择的顶点开始。其中一位代理商有一个信息，她想与其他代理商交流。所有代理商在$ g $上进行独立的随机步行，当知道该消息的代理商遇到不知道消息的代理商时，消息将传递。广播时间$ξ（g，k）$是将消息传播给所有代理商所需的时间。我们为$ξ（p_n，k）$和$ξ（c_n，k）$提供紧密的界限，几乎可以肯定地肯定地占据参数〜$ k $的整个范围。
Consider the following broadcasting process run on a connected graph $G=(V,E)$. Suppose that $k \ge 2$ agents start on vertices selected from $V$ uniformly and independently at random. One of the agents has a message that she wants to communicate to the other agents. All agents perform independent random walks on $G$, with the message being passed when an agent that knows the message meets an agent that does not know the message. The broadcasting time $ξ(G,k)$ is the time it takes to spread the message to all agents. We provide tight bounds for $ξ(P_n,k)$ and $ξ(C_n,k)$ that hold asymptotically almost surely for the whole range of the parameter~$k$.
