什么是树分解分离的概念？

Question

我想了解使用动态编程树分解的最大独立集问题。但是我不能够得到“分离”的概念在提出的算法。有人可以让我清楚这一点。提前致谢。

Answer 1

隔板是顶点的子集，其去除叶子与几个连接的部件的曲线图。的分离器是平衡的，如果每个连接组件具有小于一半相比于原始图形顶点的数量。

具有低树宽的曲线图具有小的平衡隔板。更精确地，树宽k的曲线图具有至多为k + 1个顶点的平衡隔板。

算法利用这个如下：

• 从图中删除一小均衡分离器
• 递归地找到所连接的部件的最佳解决方案
• 添加隔板再次（可能由顶点顶点），以及使用在所连接的部件的方案寻找整个图形的最佳解决方案。

为了使上述方案有效，有几个要求需要满足：

• 在第一步骤中的分离器是小的（即恒定的尺寸，）
• 在第二步骤中所连接的部件的顶点比原来的图形基本上较小数量（即，恒定的分数，例如1/2）。
• 上述性能会继承到诱导子图（否则不能有效地递归）
• 用于连接的组件部分最优解能够有效地结合，以对整个图形的最佳解决方案

这些要求由低树宽的图满足 - 除了最后一个：这个人是特定于每个优化问题，而这也正是算法设计人员在写研究论文。

（图像从上vertex separator维基百科文章获得。）