.png){kind=icon}
返回
Massively Parallel Approximate Steiner Tree Algorithms
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0218-9_9.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本工作研究了在Massively Parallel Computation（MPC）模型下的近似Steiner树问题，其中每台机器具有O(n^σ)内存，σ ∈ (0, 1)。n为图中的节点数。我们关注具有最短路径直径D和终端集S的无向连通加权图。最短路径直径是构成加权图直径的最短路径所需的最小边数。直接方法需要O(n)轮次和O(n^{3-σ/2})总内存，效率较低。为简化直接方法并降低轮次复杂度，我们设计了一个常数轮次的子程序来计算路由表，并结合代数策略与递归方法高效计算Steiner树。通过这些技术，我们提出了首个并行2(1 - 1/|S|)-近似Steiner树算法，仅需O(σ^{-1} log n + D)轮次，且内存大小和近似比相同。此外，我们将直接方法扩展到每台机器具有O(n)内存的MPC模型中，该方法需要O(log n)轮次，当D >> O(log n)时显著优于现有算法[21]。
Keyword:
The MPC model
Steiner Tree
Round Complexity
SPF
期刊
C
IF:
0
论文数:
24
被引数:
0
机构
引用论文
.png){kind=icon}
查看更多内容