minimum-spanning-tree - 線形時間で最小スパニング ツリーを再生成しますか?

Question

V 個の頂点と E 個のエッジを持つグラフ G があり、G の最小スパニング ツリー T が既にわかっている場合、E からのエッジのいくつかが取得され、それらの重みがたとえば 50 だけ増加される場合、これらのエッジはある場合とない場合があります。最小スパニング ツリーに含まれます。上記のシナリオを念頭に置いて、線形時間で新しい最小スパニング ツリーを再生成する方法はありますか? 注: 重みが変更されたエッジの数は 5 つだけです。

Answer 1

ここで SO の質問をご覧になることをお勧めします。これは、Szpira と Pan によるこの論文で直接取り上げられており、O(n) 時間で実行できると思います。