網絡流量僞多項式時間？

由於O（nW）的運行時間，我們知道正常揹包問題具有僞多項式時間。我想知道網絡流的運行時間是否爲僞多項式時間，因爲使用Ford-Fulkerson算法的網絡流的運行時間爲O（Cm）（m代表邊的數量，C代表離開起點的邊的容量之和）？網絡流量僞多項式時間？

來源

2013-10-29 CSnerd

僞多項式的概念幾乎完全取決於時間複雜度由輸入的_length_決定的事實。在這種情況下，如果您有一組以二進制表示的容量，那麼將該組容量增加一位可能會以指數方式增加「C」。從這個意義上說，算法對於輸入的單個「單位」增長按指數規律運行更長。我會說這是僞多項式。 – rliu

這裏有一個很好的參考：http://courses.csail.mit.edu/6.854/06/scribe/s9-maxflow.pdf –

是的，Ford-Fulkerson算法是一個僞多項式時間算法。它的運行時間是O（Cm），其中C是離開開始節點的容量的總和。由於寫出數字C需要O（log C）位，因此該運行時確實是多項式的，但實際上並不是多項式。但是，強多項式時間算法對於最大流量確實存在，但是，例如在時間O中運行的push-relabel算法（n ）。

希望這會有所幫助！

來源

2013-10-29 03:29:35 templatetypedef

這樣的問題是否屬於P級或NP級複雜性？網站http://www.cs.yale.edu/homes/aspnes/pinewiki/MaxFlow.html將運行時間顯示爲O（E^2 U）。你的解決方案和這個網站有什麼區別？ – LearningToCode

@LearningToCode我給出的約束比他們列出的約束更嚴格。他們說切割的最大尺寸不超過歐盟是正確的，但是你可以通過注意到由刪除s形成的切割最多具有C的容量（在我的符號中）來提供更嚴格的限制。至於這個問題是P還是NP完全的，因爲我們有最大流的算法，其運行時是強多項式（非假多項式），最大流問題肯定在P中。它可能也是NP完全的，但沒有人知道，因爲我們不知道P = NP。（續...） – templatetypedef

@LearningToCode請記住，只有*問題*可以在P或NP中，而不是*算法。* – templatetypedef

網絡流量僞多項式時間？

回答

相關問題