如何在平面圖中找到最大流量？

我知道一個算法來找到平面圖中的最小切割。如何在平面圖中找到最大流量？

作品如O（NlogN）

創建一個對偶圖，其中每個頂點對應於原始的圖形面和邊緣對應於連接兩個小面的最小邊緣。

然後您使用Dijkstra在此圖中查找最小路徑。

這樣就可以找到最小切割次數並計算流量值。

但是，我怎樣才能找到任何提供這個流量值的原始圖形邊緣集？

來源

2012-05-19 user10732

這不只是路徑中的邊緣？如果你找到路徑，你將有一組邊，對嗎？你在問什麼？ –

Emm，no。我在共軛圖中找到一條路徑。這是一組邊緣，它們形成一個切口。如果這些邊中的每一個都被破壞 - 原始圖將變成兩個斷開的圖。 – user10732

你所描述的算法只適用於無向圖（Reif算法）。哈辛和約翰遜展示瞭如何設計它來計算最大流量。最近顯示這些算法可以在O（nloglogn）時間內實現。參見G.F. Italiano，Y.Nussbaum，P.Sankowski和C.Wulff-Nilsen在無向平面圖中用於最小切割和最大流動的改進算法。在Proc。第43屆ACM研討會計算（STOC），聖何塞的理論，2011年

在定向的平坦

圖目前最快的算法運行在O（N log n）的見 http://web.engr.oregonstate.edu/~glencora/papers/other/Borradaile08-thesis-dissertation.pdf或 http://compgeom.cs.uiuc.edu/~jeffe/pubs/parshort.html

來源

2012-05-19 19:44:14

如何在平面圖中找到最大流量？

回答

相關問題