ポスト

二部マッチングを最大流で解くとき, 最大流は高々Nだからedmonds-karpとかdinicよりford-fulkersonの方が計算量的には早いみたいなことになる? それとも二部グラフのDAGだと前者ももっと改善できる?

メニューを開く

はまお@hamao_0820

みんなのコメント

メニューを開く

Ford-Fulkerson は最大フローを F 、辺数を m とするとき O(Fm) ですが、 Dinic も O(Fm) ではあるので、 Dinic が Ford-Fulkerson より遅いことは(定数倍以外では)ありません

メニューを開く

計算量的には -> 計算量のオーダー的には

はまお@hamao_0820

人気ポスト

もっと見る
Yahoo!リアルタイム検索アプリ