minimum-spanning-tree - 在线性时间内重新生成最小生成树？

Question

如果有一个图 G 有 V 个顶点和 E 个边，并且我已经知道 G 的最小生成树 T，然后如果从 E 中取出一些边并且它们的权重增加了 50，那么这些边可能会也可能不会在最小生成树中。牢记上述情况，有没有办法在线性时间内重新生成新的最小生成树？注意：权重被修改的边数只有 5 个。

Answer 1

您可能想在此处查看 SO 问题。我相信 Szpira & Pan 在这篇论文中直接解决了这个问题，并且可以在 O(n) 时间内完成。