动态图中的最大流量
我正在寻找快速算法来计算动态图中的最大流量（添加/删除具有相关边的节点到图）。即我们在 G 中具有最大流量，现在添加/删除了相关边的新节点，我不喜欢重新计算新图的最大流量，事实上，我想使用该图以前的可用结果。
任何不太消耗时间/内存的预处理都是合适的。
最简单的想法是重新计算流量。
另一个简单的想法是这样的，保存之前最大流计算中使用的所有增广路径，现在为了添加顶点v，我们可以找到从源开始的简单路径（在上一步更新的容量图中），转到 v 然后转到目的地，但问题是这条路径应该很简单，对于这种情况，我找不到比 O(n*E) 更好的路径。 （如果只有一条路径或路径不相交，这可以在 O(n+E) 中完成，但事实并非如此）。
另外，对于删除节点，上述想法不起作用。
另外，我的问题与另一个看起来动态边缘的问题无关添加/删除。
I'm looking for fast algorithm to compute maximum flow in dynamic graphs (adding/deleting node with related edges to graph). i.e we have maximum flow in G now new node added/deleted with related edges, I don't like to recalculate maximum flow for new graph, in fact, I want use previous available results for this graph.
Any preprocessing which isn't very time/memory consumer is appropriated.
Simplest idea is recalculating the flow.
Another simple idea is as this, save all augmenting paths which used in previous maxflow calculation, now for adding vertex v, we can find simple paths (in updated capacity graph by previous step) which start from source, goes to v then goes to destination, but problem is this path should be simple, I couldn't find better than O(n*E) for this case. (if it was just one path or paths was disjoint, this can be done in O(n+E), but it's not so).
Also for removing node above idea doesn't work.
Also my question is not related to another question which looks on dynamic edges adding/removing.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
为了添加顶点 v，使用旧的 Flow f 并计算残差图，然后通过 DFS OutDeg(v) 次获得增广路径。
为了删除顶点 v - 计算离开 v 的所有流量，假设离开 v 的流量之和是 a，然后在 (a>0) 找到一条从 s 到 t 的路径 P，该路径 P 穿过 v，并减少 f(P ）从流和从a。
我认为这应该有所帮助......我对添加和删除更加确定，所以我喜欢在评论中得到纠正:)
For adding Vertex v,Use the old Flow f and compute the Residual Graph, then get an Augmenting Path by DFS OutDeg(v) times.
For removing a Vertex v - compute all the flow thats leaving v, say the sum of flow leaving v is a, then while (a>0) find a path P from s to t that is going thro v, and reduce f(P) from the flow and from a.
i think that should help... im more sure on the addition then on the remove, so id love to get corrected in comments :)
要动态添加顶点
v及其关联边E：1) 将
v本身添加到图中。由于它没有边缘，因此不会影响最大流量。2) 使用 这个问题
执行相反的操作来删除顶点及其关联的边。
To dynamically add a vertex
vand its associated edgesE:1) Add
vby itself to the graph. Since it has no edges, it cannot affect the maximum flow.2) Add the associated edges
Eto the graph, one at a time, using the algorithm from this questionDo the reverse for deleting a vertex and its associated edges.
我在 CSTheory.StackExchange 中提出了这个问题，对于添加节点，正如我与其他人讨论的那样，我发现重新计算比其他已知算法更快，因为重新计算在半稀疏图（残差图）上运行，所以它对于删除节点也足够快，有一个好的答案，将节点（想要删除的）分为两个集合，v_in和v_out，并计算残差图上从v_in到v_out的流量，然后通过添加无限再次计算残差图中从v_in到v_out的流量源和目的地之间的边缘。 （最后比较它们的差异并更新残差图）。
您可以在动态图中增量最大流量。
I asked this question in CSTheory.StackExchange, For Adding node as I discussed with others I found recalculating is faster than other known algorithms, because recalculation runs on semi sparse graph (residual graph) so it's fast enough also for removing node, there was a good answer, dividing node (which wants to be removed) into two sets, v_in and v_out and calculating flow on residual graph from v_in to v_out, and again calculating flow in residual graph from v_in to v_out by adding infinite edge between source and destination. (and finally comparing their difference and updating residual graph).
You can see related Q/A and discussions in Incremental Maximum Flow in Dynamic graphs.