| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] |
¡@
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 = (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)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.
Received September 21, 2004; revised December 10, 2004; accepted January 17, 2005.
Communicated by Gen-Huey Chen.
* This work was supported by Chungshan Institute of Science and Technology under the ¡§Wide Band Mobile
Communication System Integration Technology¡¨ project, No. 95-EC-17-A-03-R7-02C5 and NSC 95-2524-
S-008-001 project.