论文标题
通过超图二分分解来唤醒最短的路径
Beeping Shortest Paths via Hypergraph Bipartite Decomposition
论文作者
论文摘要
在两个网络节点之间构建最短路径是分布式计算的基本任务。这项工作开发了用于在预定源节点和一组任意目标节点组之间随机蜂鸣网络中构建最短路径的方案。我们的第一个方案在$ O（D \ log \ log \ log n + \ log^3 n）$ rounds中以高概率构建了通往任意目标的最短路径。我们的第二个方案构建了多个最短路径，每个目的地一个一个最短的路径，以$ o（d \ log^2 n + \ log^3 n）$ rounds具有高概率。 我们的方案是基于将上述最短路径构造任务减少到分解为两部分超图中的分解：我们制定了一个蜂鸣式程序，该过程将（多项式）超ghyperghaph $ h =（v_h，e_h，e_h）$ k = up cop $ k = fum^cop^2 n）划分了（多项式）超边缘集合。 f_k = e_h $使得（sub-）hypergraph $（v_h，f_i）$在某种意义上是两部分，因为存在一个顶点子集$ u \ subseteq v $，因此$ | u \ cap e | = f_i $中的每个$ e \ 1 $。事实证明，此过程在蜂鸣器模型下加速最短路径构建体有助于。
Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in $O (D \log\log n + \log^3 n)$ rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in $O (D \log^2 n + \log^3 n)$ rounds with high probability. Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the (polynomially-large) hyperedge set of a hypergraph $H = (V_H, E_H)$ into $k = Θ(\log^2 n)$ disjoint subsets $F_1 \cup \cdots \cup F_k = E_H$ such that the (sub-)hypergraph $(V_H, F_i)$ is bipartite in the sense that there exists a vertex subset $U \subseteq V$ such that $|U \cap e| = 1$ for every $e \in F_i$. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.
