[HTML][HTML] Approximating the weight of shallow Steiner trees
G Kortsarz, D Peleg - Discrete Applied Mathematics, 1999 - Elsevier
Discrete Applied Mathematics, 1999•Elsevier
This paper deals with the problem of constructing Steiner trees of minimum weight with
diameter bounded by d, spanning a given set of ν vertices in a graph. Exact solutions or
logarithmic ratio approximation algorithms were known before for the cases of d⩽ 5. Here
we give a polynomial-time approximation algorithm of ratio O (log ν) for constant d, which is
asymptotically optimal unless P= NP, and an algorithm of ratio O (νε), for any fixed 0< ε< 1,
for general d.
diameter bounded by d, spanning a given set of ν vertices in a graph. Exact solutions or
logarithmic ratio approximation algorithms were known before for the cases of d⩽ 5. Here
we give a polynomial-time approximation algorithm of ratio O (log ν) for constant d, which is
asymptotically optimal unless P= NP, and an algorithm of ratio O (νε), for any fixed 0< ε< 1,
for general d.
This paper deals with the problem of constructing Steiner trees of minimum weight with diameter bounded by d, spanning a given set of ν vertices in a graph. Exact solutions or logarithmic ratio approximation algorithms were known before for the cases of d⩽5. Here we give a polynomial-time approximation algorithm of ratio O ( log ν) for constant d, which is asymptotically optimal unless P=NP, and an algorithm of ratio O(νε), for any fixed 0<ε<1, for general d.
Elsevier