私は、有向で強く接続されたグラフであるグラフ G を持っています。グラフ内の S と T のすべてのペアを意味する、頂点のすべてのペアの最小カットを見つけるように求められます。これは、O(m 2 × n 2 ) 時間で実行する必要があります。
私が思いついた最善の方法は、すべての頂点を S と見なし、各 S について他のすべての頂点を T と見なし、それらのそれぞれについてフォード-フルカーソン アルゴリズムを実行し、最小カットを見つけることでした。しかし、私が間違っていなければ、このアルゴリズムは O(m 2 × n 2 × C) の複雑さを持ちます。
このタスクを O(m 2 × n 2 ) 時間で行うにはどうすればよいでしょうか? それは可能ですか？