algorithm - 用于在树中查找支配集的多项式时间算法

Question

令 G = (V,E) 为无向图。 G 中节点的子集 S ⊆ V 称为“支配集”，如果对于所有 v ∈ V，我们有 v ∈ S 或存在某个节点 u ∈ S 使得 (u,v) ∈ E。换句话说，每个V\S 中的节点通过边连接到 S 中的某个节点。给定 V 的节点上的非负权重 w(v)，目标是找到 G 中的最小权重支配集。(注意:这个问题是在一般图中已知是 NP-Hard)当G是一棵树时，我们需要设计一个POLYNOMIAL时间算法来解决这个问题。

在维基上看到Steiner tree problem，跟这个有点关系，但还是一头雾水。

我们需要怎么做？

Answer 1

我找到了这篇论文，它在第 19 页给出了树的顶点-边缘加权控制数的动态规划算法。对于“树排序”，您可以使用后序遍历排序。你将不得不稍微修改它(例如，让所有边权重为零)，你应该找到一种从 DP 矩阵构造解决方案的方法。希望这会有所帮助。

http://www.math.ntu.edu.tw/~mathlib/preprint/2011-01.pdf