最小支配集有向图

Question

http://en.wikipedia.org/wiki/Dominating_set

的现在，我有一个想法，找到它，我需要你的意见

第一：
在图形上创建一个排名系统，每个顶点有一个等级。顶点 排名为：
2 * [出边的数量] - [中数入边]

二：
改变DFS算法：让它也返回所有根的小组跨越森林（不改变的复杂性）

算法：
1.开始与所有的顶点为最小支配集
2.运行DFS与起始顶点：排名最高的顶点
3.看看根在生成森林，取最小支配集的列表并删除每个不是Spa的根的顶点nning森林
4.重复2-3与谁是留在极小支配下一个排名最高的顶点设置
5.停止，当你在极小支配上的每个顶点跑了DFS设置
6.返回它

我使用adj-list，所以DFS是O（| V | + | E |） 您对这种算法有什么看法？它会起作用吗？我可以做得更好吗？这个算法的分期最坏情况是什么？

Answer 1

它会工作吗？

编号A简单的计数器的例子是该曲线图中：

行列是[1:6, 2:-1, 3:1, 4:-1, 5:-1].在步骤2中，在运行DFS一个从顶点1.它是在生成森林的唯一根源，所以在第3步中，删除每个其他顶点并返回。但是，这不是一个主导的集合！ 5既不在控制集中的节点中，也不在其中。

该算法的摊销最坏情况是什么？

最坏的情况是O（| V | + | E | + k ），其中k是返回集的大小。你将在第一次移除除根之外的所有东西，所以通过循环的下一个O（k）次将仅需要O（k）个时间。

我可以做得更好吗？

是的，在正确性和速度。移除当前顶点的所有邻居，然后移动到仍然在集合中的下一个顶点。这将只需要O（| V | + | E |）。

看来你试图得到更接近全局最小值的东西;为此，我建议检查文献中的“最小主控集近似”。