未連接的有向圖節點的最大子集的大小？

給定一個有向圖，我怎樣才能找到最大的頂點子集的大小，使得它們中沒有兩個通過有向路徑連接？未連接的有向圖節點的最大子集的大小？

這個問題（或解決它的算法）有一個共同的名字嗎？

（提示：「根據迪爾沃思定理，這個問題實際上相當於鏈的最小數目覆蓋上一個DAG計算的傳遞閉包之後。因此，這個問題可以減少到二分圖的最大匹配。「）

如果您第一次構造傳遞閉包，那麼您尋找的子集將是該圖中的最大獨立集合。（Evgeny Kluev非常接近......） –

@j_random_hacker：是的，但得到的圖形是雙向的，所以有一個P時間解決方案。 –

你怎麼知道這是雙方？ –

我不知道這個名字，我想這是的Disjoint-set data structure

使用聯盟找到一個子問題，您可以決定所有連接圖。

最初，每個節點都在其組上。檢查每個節點並將其所有直接子節點添加到節點的組根目錄中。這是Union Find的基本功能。

然後最大的子集由每個組的一個頂點組成。在最壞的情況下，當每個節點連接到所有其他節點時，當n次檢查每個節點時，這應該取O（n2）。

2012-10-19 10:29:19

回答