- 期刊
- OpenAccess
FasterDSP: A Faster Approximation Algorithm for Directed Steiner Tree Problem
並列摘要
Given a weighted directed graph G=(V, E, c), where c: E→R(superscript +) is an edge cost function, a subset X of vertices (terminals), and a root vertex v(subscript r), the directed Steiner tree problem (DSP) asks for a minimum-cost tree which spans the paths from root vertex v(subscript 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(superscript 1/l) in (The symbol is abbreviated) (n(superscript l)k(superscript 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, (The symbol is abbreviated) (n(superscript l)k(superscript 2l)k+nm), where m is the number of edges, and an amended √8k-δln k factor for the 2-level Steiner tree, where δ=√6-2(The symbol is abbreviated)0.4494.