algorithm - 动态图中的最大流

Question

我正在寻找快速算法来计算动态图中的最大流(向图中添加/删除具有相关边的节点)。即我们在 G 中有最大流，现在新节点添加/删除了相关边，我不喜欢重新计算新图的最大流，事实上，我想使用该图以前的可用结果。

任何不是非常耗费时间/内存的预处理都是合适的。

最简单的想法是重新计算流量。

另一个简单的想法是这样的，保存之前最大流计算中使用的所有增广路径，现在添加顶点v，我们可以找到简单的路径(在上一步更新的容量图中)开始从源头，转到 v 然后转到目的地，但问题是这条路径应该很简单，对于这种情况，我找不到比 O(n*E) 更好的方法了。 (如果只有一条路径或路径不相交，这可以在 O(n+E) 中完成，但事实并非如此。

同样对于移除上述节点的想法也不起作用。

我的问题也与another question which looks on dynamic edges adding/removing无关.

Answer 1

对于添加顶点 v，使用旧的流 f 并计算残差图，然后通过 DFS OutDeg(v) 次获得增广路径。

为了删除顶点 v - 计算所有离开 v 的流，假设离开 v 的流的总和是 a，然后在 (a>0) 找到从 s 到 t 的路径 P，该路径经过 v，并减少f(P) 来自流和来自 a.

我认为这应该有所帮助...我更确定添加然后删除，所以我喜欢在评论中得到纠正 :)