用于在树中查找支配集的多项式时间算法 [英] polynomial-time algorithm for finding dominating set in a tree

问题描述

设 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时间算法来解决这个问题.

Let G = (V,E) be an undirected graph. A subset S ⊆ V of nodes in G is called a "dominating set" if for all v ∈ V, we have v ∈ S or there is some node u ∈ S such that (u,v) ∈ E. In other words every node in V S is connected by an edge to some node in S. Given non-negative weights w(v) on the nodes of V the goal is to find a minimum-weight dominating set in G. (Note: This problem is known to be NP-Hard in general graphs) We need to design a POLYNOMIAL time algorithm fir this problem when G is a tree.

我在 Wiki 上阅读了有关 Steiner 树问题的内容，这与此有些相关，但仍然很困惑.

I read about Steiner tree problem on Wiki, which is somewhat related to this, but still confused.

我们需要怎么做?

推荐答案

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

I found this paper, which gives a dynamic programming algorithm for the vertex-edge weighted domination number of a tree on page 19. For the "tree ordering", you can use a post-order traversal ordering. You will have to modify it a bit (e.g., let all edge weights be zero), and you should find a way to construct the solution from the DP matrix. Hope this helps.

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

这篇关于用于在树中查找支配集的多项式时间算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！