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**

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 *v _{r}*, the directed Steiner tree
problem (DSP) asks for a minimum-cost tree which spans the paths from root vertex

*
Keywords:
*
directed Steiner tree, approximation algorithm, multicast distribution tree,
content delivery network, multicast routing

Retrieve PDF document (**200611_07.pdf**)

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.