|
假设:一个图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)
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-4-24 09:43
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社