This work studies the approximate Steiner tree problem in the Massively Parallel Computation (MPC) model where each machine has \(O(n^{\sigma })\) memory and \(\sigma \in (0,1)\) . n is the number of nodes in a graph. We focus on the undirected connected weighted graphs with shortest path diameter D and a terminal set S. The shortest path diameter is the minimum number of edges required for the shortest path constituting a weighted graph’s diameter. The straightforward approach takes O(n) rounds and \(O(n^{3-\sigma /2})\) total memory, which is inefficient. To simplify the straightforward approach and reduce the round complexity, we design a constant-round subroutine to compute the routing table and combine algebraic strategies with recursive methods to compute the Steiner tree efficiently. By these techniques, we give the first parallel \(2(1-1/|S|)\) -approximate Steiner tree algorithm that requires \(O(\sigma ^{-1}\log n+D)\) rounds with the same memory size and the same approximation ratio. Moreover, we extend the straightforward approach to the MPC model with O(n) memory per machine, which takes \(O(\log n)\) rounds and significantly outperforms the existing algorithm [21] when \(D\gg O(\log n)\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Massively Parallel Approximate Steiner Tree Algorithms

  • Chilei Wang,
  • Qiang-Sheng Hua,
  • Hai Jin

摘要

This work studies the approximate Steiner tree problem in the Massively Parallel Computation (MPC) model where each machine has \(O(n^{\sigma })\) memory and \(\sigma \in (0,1)\) . n is the number of nodes in a graph. We focus on the undirected connected weighted graphs with shortest path diameter D and a terminal set S. The shortest path diameter is the minimum number of edges required for the shortest path constituting a weighted graph’s diameter. The straightforward approach takes O(n) rounds and \(O(n^{3-\sigma /2})\) total memory, which is inefficient. To simplify the straightforward approach and reduce the round complexity, we design a constant-round subroutine to compute the routing table and combine algebraic strategies with recursive methods to compute the Steiner tree efficiently. By these techniques, we give the first parallel \(2(1-1/|S|)\) -approximate Steiner tree algorithm that requires \(O(\sigma ^{-1}\log n+D)\) rounds with the same memory size and the same approximation ratio. Moreover, we extend the straightforward approach to the MPC model with O(n) memory per machine, which takes \(O(\log n)\) rounds and significantly outperforms the existing algorithm [21] when \(D\gg O(\log n)\) .