TY - JOUR

T1 - FasterDSP

T2 - A faster approximation algorithm for directed steiner tree problem

AU - Hsieh, Ming I.

AU - Wu, Eric Hsiao Kuang

AU - Tsai, Meng Feng

PY - 2006/11

Y1 - 2006/11

N2 - 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 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)kl1 in O(n lk2l) 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 - δ In k factor for the 2-level Steiner tree, where δ = √6 - 2 = 0.4494.

AB - 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 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)kl1 in O(n lk2l) 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 - δ In k factor for the 2-level Steiner tree, where δ = √6 - 2 = 0.4494.

KW - Approximation algorithm

KW - Content delivery network

KW - Directed steiner tree

KW - Multicast distribution tree

KW - Multicast routing

UR - http://www.scopus.com/inward/record.url?scp=33751513802&partnerID=8YFLogxK

M3 - 期刊論文

AN - SCOPUS:33751513802

SN - 1016-2364

VL - 22

SP - 1409

EP - 1425

JO - Journal of Information Science and Engineering

JF - Journal of Information Science and Engineering

IS - 6

ER -