3

考虑一个加权图 G=(V,E,w)。我们得到一组顶点 V_i 的子集。

斯坦纳森林是一个森林,对于每个顶点子集 V_i 将这个子集中的所有顶点与一棵树连接起来。

示例:只有一个子集 V_1 = V。在这种情况下,Steiner 森林是整个图的生成树。

示例:图 P4(具有 4 个顶点的路径)和两个子集:V_1 = {v1, v4} 和 V_2 = {v2, v3}。此示例的 Steiner 树是整个图。

理论够了。很难找到这样一个重量最小的森林(NP-complete)。你知道任何更快的近似算法来找到这样一个非最优权重的森林吗?

4

2 回答 2

4

Vijay Vazirani 在 Approximation Algorithms 的第 20 章描述了生成 Steiner Forest 的模式。分析使用 LP 对偶,他用它来确定算法的因子:

(这是一个因子 2 算法,但实际上它可能运行得很好)

逼近算法

另外:请参阅 22.5 中的注释,其中描述了三篇论文以供进一步阅读,包括对该主题的调查。

于 2010-04-20T18:04:26.077 回答
0

也许您可以将此问题重述为其他 NP 完全问题,您知道任何次优算法?不过,这只是一个猜测——我无法用我非常有限的数学技能找到这样的映射:)

于 2010-04-20T14:25:26.900 回答