设 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 是一棵树时，我们需要设计一个多项式时间算法来解决这个问题。
我在维基上读到了斯坦纳树问题，这与此有些相关，但仍然很困惑。
我们需要怎样做呢？
我找到了这篇论文，第19页给出了树的点边加权支配数的动态规划算法。对于“树排序”，可以使用后序遍历排序。您必须对其进行一些修改（例如，让所有边权重为零），并且您应该找到一种从 DP 矩阵构建解决方案的方法。希望这可以帮助。
http://www.math.ntu.edu.tw/~mathlib/preprint/2011-01.pdf
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
