.png){kind=icon}
.png){kind=icon}
Return
Massively Parallel Approximate Steiner Tree Algorithms
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0218-9_9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 is an element of (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 >> O(log n).
Keywords:
The MPC model
Steiner Tree
Round Complexity
SPF
Journal
C
IF:
0
Papers:
24
Citations:
0