代码之家 › 专栏 › 技术社区 › Tadeusz A. KadÅubowski

一种寻找斯坦纳森林的近似算法

approximation tree graph-theory algorithm

Tadeusz A. KadÅubowski · 技术社区 · 16 年前

考虑一个加权图g=(v,e,w)。我们得到一个顶点子集的族。

Steiner林是一个林,对于顶点的每个子集,v_i将该子集中的所有顶点与树连接起来。

示例:只有一个子集v_1=v。在本例中,steiner林是整个图的生成树。

示例:图P4(具有4个顶点的路径)和两个子集:v_1 v1、v4和v_2 v2、v3。本例中的Steiner树是整个图。

足够的理论。找到这样一个重量最小的森林是困难的(NP完全)。你知道有什么更快的近似算法可以找到这样一个非最优权重的森林吗?

2 回复 | 直到 16 年前

cjb 16 年前

维杰瓦齐拉尼的近似算法第20章描述了一种生成斯坦纳森林的模式。分析使用LP对偶性,他使用它来确定算法的因素:

(这是一个因子-2算法,但在实践中,它的价格可能相当高)

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

Victor Sorokin 16 年前

也许你可以把这个问题重述为其他NP完备,你知道任何次优算法吗? 不过,这只是一个猜测——我的数学能力很有限,找不到这样的地图。)

推荐文章

Bala Ji · 以下BFS的实施效率如何?

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

NeoExceptCodeBad · 如果我有很多垂直线,我如何找到它们的边缘?

2 年前

VIAGC · 使用相邻列表创建图形

2 年前

Alexander · 提取节点属性最大值的键

3 年前

R3FL3CT · 如何在Python中将一组网站及其链接转换为有向图?

3 年前

Szyszka947 · 我什么时候可以假设Dijkstra算法中的某个顶点已经完成了最短路径

3 年前

amonroejj · 实现基于节点的工作流的一般原则,如Unreal、Blender、Alteryx等?

8 年前

quantummidget · 正在查找BFS父关系数组

8 年前