刘兴武
读书笔记一则:图上2-近似的最小斯坦纳树算法
2022-12-8 00:32
阅读:418

假设:一个图G=(V,E,d),其中d是非负边长,顶点子集S是Terminal集合,希望找到G中的一棵子树,包含S,且最小。

算法:

Step 1: 对S中每对点(u,v),计算在G中的最短路P(u,v)及其长度d'(u,v),得到S上的带权完全图G'=(S,E',d');

Step 2: 构造G'的最小生成树T;

Step 3: 把T中的所有边(u,v)恢复为最短路P(u,v),得到G的子图T';

Step 4: 在T'中构造最小生成树T'';

Step 5: 在T''中去掉不必要的顶点,得到一棵包含S的树,作为输出。

近似比的证明非常巧妙。

 Reference: 

Kou, L., Markowsky, G., Berman, L.: A Fast Algorithm for Steiner Trees. Acta Inf. 15, 141–145 (1981)


转载本文请联系原作者获取授权,同时请注明本文来自刘兴武科学网博客。

链接地址:https://wap.sciencenet.cn/blog-3526448-1366987.html?mobile=1

收藏

分享到:

下一篇
当前推荐数:0
推荐到博客首页
网友评论0 条评论
确定删除指定的回复吗?
确定删除本博文吗?