Approximating shallow-light trees
Approximating shallow-light trees
复制标题
近似浅光树
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
G. Kortsarz;D. Peleg
本文研究了在图中生成由{nu}个顶点组成的给定集合V的最小权值、直径以d为界的斯坦纳树的构造问题。对于d {le} 5的情况，精确解或对数比率近似算法以前是已知的。对于常数d，我们给出了比率d log {nu}的多项式时间逼近算法，对于任意固定的0 < {epsilon} < 1，我们给出了比率{nu}{sup {epsilon}}的多项式时间逼近算法。
This paper deals with the problem of constructing Steiner trees of minimum weight with diameter bounded by d, spanning a given set V of {nu} vertices in a graph. Exact solutions or logarithmic ratio approximation algorithms were known before for the cases of d {le} 5. Here we give a polynomial time approximation algorithm of ratio d log {nu} for constant d, and an algorithm of ratio {nu}{sup {epsilon}}, for any fixed 0 < {epsilon} < 1, for general d.