我正在寻找快速算法来计算动态图中的最大流量（添加/删除具有相关边的节点到图）。即我们在 G 中有最大流量现在添加/删除了相关边的新节点，我不喜欢重新计算新图的最大流量，事实上，我想使用该图以前可用的结果。
任何不是很消耗时间/内存的预处理都会被占用。
最简单的想法是重新计算流量。
另一个简单的想法是这样，保存之前 maxflow 计算中使用的所有扩充路径，现在添加 vertex v，我们可以找到从源开始的简单路径（在上一步更新的容量图中），v然后到达目的地，但是问题是这条路径应该很简单，对于这种情况，我找不到比 O(n*E) 更好的方法。（如果只是一条路径或路径不相交，这可以在 O(n+E) 中完成，但事实并非如此）。
同样对于删除上述想法的节点也不起作用。
此外，我的问题与另一个关于动态边缘添加/删除的问题无关。
添加 Vertex v，使用旧的 Flow f 并计算 Residual Graph，然后通过 DFS OutDeg(v) 次获得 Augmenting Path。
移除一个顶点 v - 计算所有离开 v 的流量，假设离开 v 的流量总和为 a，然后在 (a>0) 时找到一条从 s 到 t 的路径 P，该路径经过 v，并减少 f(P ) 从流和从 a。
我认为这应该会有所帮助......我更确定添加然后删除，所以我喜欢在评论中得到纠正:)
要动态添加顶点v及其关联的边E：
1)v自行添加到图表中。由于它没有边，它不会影响最大流量。
2）使用this questionE中的算法将关联的边一次添加到图中
执行相反的操作以删除顶点及其关联的边。
我在 CSTheory.StackExchange 中问了这个问题，对于添加节点，正如我与其他人讨论的那样，我发现重新计算比其他已知算法更快，因为重新计算在半稀疏图（残差图）上运行，因此对于删除节点也足够快，有一个好的答案，将节点（要删除的节点）分成两组，v_in 和 v_out 并计算从 v_in 到 v_out 的残差图上的流量，并通过在源和目标之间添加无限边再次计算从 v_in 到 v_out 的残差图中的流量。（最后比较它们的差异并更新残差图）。您可以在动态图中的增量最大流量中查看相关的 Q/A 和讨论 。