Sae*_*iri 10 algorithm graph max-flow
我正在寻找快速算法来计算动态图形中的最大流量(添加/删除具有相关边缘的节点到图形).即我们在G中有最大流量,现在添加/删除了相关边缘的新节点,我不想重新计算新图形的最大流量,事实上,我想使用此图形的先前可用结果.
任何非时间/内存消费者的预处理都是适当的.
最简单的想法是重新计算流量.
另一个简单的想法就是这样,保存以前maxflow计算中使用的所有扩充路径,现在用于添加顶点v,我们可以找到从源开始的简单路径(在前一步骤的更新容量图中),v然后转到目的地,但是问题是这条路应该简单,我找不到比O(n*E)更好的情况.(如果它只是一条路径或路径是不相交的,这可以在O(n + E)中完成,但事实并非如此).
另外对于删除节点以上的想法不起作用.
此外,我的问题与另一个关于动态边缘添加/删除的问题无关.
我在 CSTheory.StackExchange 中提出了这个问题，对于添加节点，正如我与其他人讨论的那样，我发现重新计算比其他已知算法更快，因为重新计算在半稀疏图（残差图）上运行，所以它对于删除节点也足够快，有一个好的答案，将节点（要删除的节点）分为两个集合，v_in 和 v_out，并计算残差图上从 v_in 到 v_out 的流量，然后通过在源和目标之间添加无限边来再次计算残差图中从 v_in 到 v_out 的流量。（最后比较它们的差异并更新残差图）。您可以在动态图中的增量最大流量中查看相关问答和讨论 。