## Abstract

Given a weighted directed graph G = (V, E, c), where c : E → R ^{+} is an edge cost function, a subset X of vertices (terminals), and a root vertex v_{r}, the directed Steiner tree problem (DSP) asks for a minimum-cost tree which spans the paths from root vertex v_{r} to each terminal. Charikar et al.'s algorithm is well-known for this problem. It achieves an approximation guarantee of l(l - 1)k^{l1} in O(n ^{l}k^{2l}) 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(n^{l}k^{l} + n^{2}k + nm), where m is the number of edges, and an amended √8k - δ In k factor for the 2-level Steiner tree, where δ = √6 - 2 = 0.4494.

Original language | English |
---|---|

Pages (from-to) | 1409-1425 |

Number of pages | 17 |

Journal | Journal of Information Science and Engineering |

Volume | 22 |

Issue number | 6 |

State | Published - Nov 2006 |

## Keywords

- Approximation algorithm
- Content delivery network
- Directed steiner tree
- Multicast distribution tree
- Multicast routing