多くの小さなDAGS（8〜12ノード、20〜60エッジ）の最小カット問題を非常に迅速に解決したいと思います。最善の解決策は、最大フローを解き、そこからカットを推定することであるように見えます。理論的および経験的タイミング比較の両方が利用可能な最大フローアルゴリズムはかなりありますが、これらはすべて、グラフがどんどん大きくなるにつれてパフォーマンスが興味深いことを前提としています。また、使用される複雑なデータ構造のセットアップ時間は非常に長くなる可能性があることもよく言われます。それで、注意深く最適化された実装（おそらくC ++で）を考えると、どのアルゴリズムが小さなグラフでの初期化と実行に最も速いことがわかりますか？（私の素朴な仮定は、エドモンズ・カープはおそらくデータ構造の点で同じくらい単純なので、より複雑なアルゴリズムを打ち負かすだろうということですが、それは単なる推測です。）