论文标题
计算混合网络模型中的最短路径和直径
Computing Shortest Paths and Diameter in the Hybrid Network Model
论文作者
论文摘要
$ \ Mathsf {Hybrid} $模型，在[Augustine等人，SODA '20]中引入，为允许多种通信模式的网络提供了理论基础。该模型遵循同步消息传递的原理，而允许节点使用\ textit {两个}根本不同的通信模式。首先，一种本地模式，节点可以每回合在本地通信图$ g $（类似于$ \ mathsf {local} $模型）的边缘上交换任意信息。其次，每个节点都可以通过网络中的任意节点来交换每个节点$ o（\ log n）$消息的$ o（\ log n）$消息。 $ \ mathsf {hybrid} $模型打算反映许多真实混合网络的条件，在这种情况下，高频带宽度但固有的本地通信与高度灵活的全局通信和受限的带宽相结合。 我们通过研究计算本地通信图$ g $的最短路径和直径的复杂性，继续探索$ \ mathsf {hybrid} $模型的功率和局限性。我们从[Augustine等人，SODA '20]的所有最短路径问题（APSP）上改进了已知的上限，并提供了算法，以近似于$ k $ source最短路径问题的解决方案（$ k $ $ k $ -ssssp）。我们证明了我们对APSP和$ K $ -SSP的结果几乎很紧（取决于多形因素）。此外，我们为精确的单一源最短路径问题提供了改进的算法，用于较大直径的图。对于近似本地通信网络直径的问题，我们给出了第一个非平凡的上限。该上限与确切直径问题的下限相辅相成。
The $\mathsf{HYBRID}$ model, introduced in [Augustine et al., SODA '20], provides a theoretical foundation for networks that allow multiple communication modes. The model follows the principles of synchronous message passing, whereas nodes are allowed to use \textit{two} fundamentally different communication modes. First, a local mode where nodes may exchange arbitrary information per round over edges of a local communication graph $G$ (akin to the $\mathsf{LOCAL}$ model). Second, a global mode where every node may exchange $O(\log n)$ messages of size $O(\log n)$ bits per round with arbitrary nodes in the network. The $\mathsf{HYBRID}$ model intends to reflect the conditions of many real hybrid networks, where high-bandwidth but inherently local communication is combined with highly flexible global communication with restricted bandwidth. We continue to explore the power and limitations of the $\mathsf{HYBRID}$ model by investigating the complexity of computing shortest paths and diameter of the local communication graph $G$. We improve on the known upper bound for the exact all pairs shortest paths problem (APSP) from [Augustine et al., SODA '20] and provide algorithms to approximate solutions for the $k$ source shortest paths problem ($k$-SSSP). We demonstrate that our results for APSP and $k$-SSP are almost tight (up to poly-logarithmic factors). Furthermore, we give an improved algorithm for the exact single source shortest paths problem for graphs with large diameter. For the problem of approximating the diameter of the local communication network we give the first non-trivial upper bound. This upper bound is complemented by a lower bound for the exact diameter problem.
