Loading...
Please wait, while we are loading the content...
Similar Documents
Fasterdsp: a faster approximation algorithm for directed steiner tree problem (2006).
| Content Provider | CiteSeerX |
|---|---|
| Author | Tsai, Meng-Feng Hsieh, Ming-I. Wu, Eric Hsiao-Kuang |
| 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 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 1 an approximation guarantee of ( 1) l ll − k 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 − δ lnk factor for the 2-level Steiner tree, where δ = |
| File Format | |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Faster Approximation Algorithm Minimum-cost Tree Fixed Level Weighted Directed Graph Dsp Algorithm Time Complexity Approximation Guarantee 2-level Steiner Tree Directed Steiner Tree Problem Lnk Factor Great Amount Root Vertex Vr Edge Cost Function |
| Content Type | Text |
| Resource Type | Article |
