Search

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]