最小支配集有向圖

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 |）。

看來你試圖得到更接近全局最小值的東西;爲此，我建議檢查文獻中的「最小主控集近似」。