最大加權跨越弱連接算法DAG

是否有一種算法可以找到跨越DAG的最大權重，該算法在有向圖中弱連接，其中每個剪輯都有弱連接的集合（至少有一個從一個集合到另一個）？或者這是一個NP難題？在這個題目上一問題中沒有指定https://mathoverflow.net/questions/31864/algorithms-for-maximum-weighted-spanning-connected-dag-directed-acyclic-graph強還是弱連接，所以我想更精確。最大加權跨越弱連接算法DAG

來源

2012-12-26 vkaul11

這可能是一個更適合在cs.stackexchange.com。 – templatetypedef

Huf，我腦海中唯一想要修改Chu-Liu-Edmonds算法...... – malejpavouk

您的弱連接條件似乎是連接了底層的無向圖。這很容易;你可以使用Kruskal或Prim或任何你最喜歡的最小生成樹算法。

最小權重強連通子圖是NP完全的;注意任何這樣的子圖至少有| V |邊緣並且它具有| V |當且僅當它是哈密爾頓循環時。

您可能希望選擇一個頂點作爲「根」，並要求從子圖的每個頂點到根都有一條路徑。這是「最小化白蟻」問題。作爲@matejpavouk指出，對於這種因楚，劉和埃德蒙茲二次算法。

來源

2012-12-27 00:50:08 tmyklebu

我可以找到一個有四個頂點的例子，其中Krusal或Prim無法找到沒有定向循環的最大加權子圖。「你的弱連接條件似乎是連接了底層的無向圖。」 IT只是意味着在兩組任意剪輯之間至少有一個有向邊。在這一點上，有向圖和無向圖算法之間存在差異，所以Kruskal和Prim失敗。 – vkaul11

「在兩組任意切割之間至少存在一個有向邊」意味着，如果我選擇既不是空也不是所有頂點的集合S，那麼在S和V-S之間存在邊，右？這正是「底層圖的連通性」和Kruskal/Prim在那裏的工作。如果你想從S到V-S的邊緣和從V-S到S的邊緣，這是強大的連通性，你的問題是NP完全的。如果你的意思是別的，請明確指出（並且最好給出一個例子，說明爲什麼你想要的與底層圖的連通性不一樣。） – tmyklebu

希望thisn't爲時已晚。對於上述案例，克魯斯卡爾和普林姆都很容易失敗。考慮一個2節點圖：A→B（權重10），B→A（權重6），B→A（權重6）（是：從B到A的兩個邊;圖中沒有任何內容排除了！）。克魯斯卡爾首先會選擇A - > B的邊緣並卡住。 Prim會選擇從B到A的邊緣之一，然後卡住。最大。加權的非循環子圖是包含從B到A的邊的圖。它是一個子圖，它是非循環的！

最佳拉維

來源

2013-09-20 22:36:44 Ravi

弱連接圖是否有從兩個頂點到另一個頂點的連接？ – Andigor

最大加權跨越弱連接算法DAG

回答

相關問題