论文标题
稀疏图中最短路径的快速混合网络算法
Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs
论文作者
论文摘要
我们考虑计算混合网络中最短路径的问题，其中节点可以利用不同的通信模式。例如，除了蜂窝网络之外，手机还可以通过蓝牙或Wi-Fi使用临时连接，以更有效地解决任务。像在这种情况下一样，不同的通信模式在范围，带宽和灵活性上可能有很大差异。我们以奥古斯丁等人的模型为基础。 [SODA '20]，通过本地和全局模式捕获了这些差异。具体而言，本地边缘模型固定的通信网络，其中$ o（1）$ o（\ log n）$的$ o（1）$可以通过每个同步回合的每个边缘发送。全局边缘形成一个集团，但是节点只能在全局边缘上最多发送和接收总共$ O（\ log n）$消息，这限制了节点仅非常稀少地使用这些边缘。我们通过呈现算法来计算最短路径和直径在稀疏图中非常有效地计算直径来证明混合网络的功能。具体来说，我们提供了仙人掌图的精确$ o（\ log n）$ time算法（即，最多在一个周期中包含每个边缘的图形），以及$ 3 $ - approximations for Graphs的$ n + o（n^{1/3}）$ edges and Arboricity $ e（n^{1/3}）$ edges and Arboricity $ o（\ log o（\ log log n n）$。对于这些图形类别，我们的算法提供了指数级的解决方案，该解决方案比该模型中一般图的最著名算法更快。除了最短的路径之外，我们还为混合网络提供了各种有用的工具和技术，这可能引起独立感兴趣。
We consider the problem of computing shortest paths in hybrid networks, in which nodes can make use of different communication modes. For example, mobile phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular network to solve tasks more efficiently. Like in this case, the different communication modes may differ considerably in range, bandwidth, and flexibility. We build upon the model of Augustine et al. [SODA '20], which captures these differences by a local and a global mode. Specifically, the local edges model a fixed communication network in which $O(1)$ messages of size $O(\log n)$ can be sent over every edge in each synchronous round. The global edges form a clique, but nodes are only allowed to send and receive a total of at most $O(\log n)$ messages over global edges, which restricts the nodes to use these edges only very sparsely. We demonstrate the power of hybrid networks by presenting algorithms to compute Single-Source Shortest Paths and the diameter very efficiently in sparse graphs. Specifically, we present exact $O(\log n)$ time algorithms for cactus graphs (i.e., graphs in which each edge is contained in at most one cycle), and $3$-approximations for graphs that have at most $n + O(n^{1/3})$ edges and arboricity $O(\log n)$. For these graph classes, our algorithms provide exponentially faster solutions than the best known algorithms for general graphs in this model. Beyond shortest paths, we also provide a variety of useful tools and techniques for hybrid networks, which may be of independent interest.
