2021-05-02から1日間の記事一覧
Global Minimum Cut Stoer-Wagner algorithm 無向グラフに対して、あらゆるペア(s, t)のカットの中で最小の s-t-カットを求める。 問題 重み付無向グラフが与えられる。各頂点にSかTを割り当てたとき、一端がSでもう一端がTの辺の重みの総和をその「割り当て…
Global Minimum Cut Stoer-Wagner algorithm 無向グラフに対して、あらゆるペア(s, t)のカットの中で最小の s-t-カットを求める。 問題 重み付無向グラフが与えられる。各頂点にSかTを割り当てたとき、一端がSでもう一端がTの辺の重みの総和をその「割り当て…