JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19]


Journal of Information Science and Engineering, Vol. 22 No. 6, pp. 1409-1425


FasterDSP: A Faster Approximation Algorithm for Directed Steiner Tree Problem


Ming-I Hsieh, Eric Hsiao-Kuang Wu and Meng-Feng Tsai
Department of Computer Science and Information Engineering 
National Central University 
Chungli, 320 Taiwan 
E-mail: mihs@wmlab.csie.ncu.edu.tw 
E-mail: {hsiao; mftsai}@csie.ncu.edu.tw


    Given a weighted directed graph G = (VEc), where c : E → R+ is an edge cost function, a subset X of vertices (terminals), and a root vertex vr, the directed Steiner tree problem (DSP) asks for a minimum-cost tree which spans the paths from root vertex vr to each terminal. Charikar et al.'s algorithm is well-known for this problem. It achieves an approximation guarantee of l(l - 1)kl in O(nlk2l) time for any fixed level l > 1, where l is the level of the tree produced by the algorithm, n is the number of vertices, |V|, and k is the number of terminals, |X|. However, it requires a great amount of computing power, and there are some problems in the proof of the approximation guarantee of the algorithm. This paper provides a faster approximation algorithm improving Charikar et al.'s DSP algorithm with a better time complexity, O(nlkl + n2k + nm), where m is the number of edges, and an amended 8k -δlnk factor for the 2-level Steiner tree, where δ = 6 - 2 = 0.4494.


Keywords: directed Steiner tree, approximation algorithm, multicast distribution tree, content delivery network, multicast routing

  Retrieve PDF document (JISE_200606_07.pdf)