logo标签列表

动态图中的最大流量

algorithmgraphmax-flow
10

我正在寻找一种快速算法来计算动态图中的最大流量（向图中添加/删除包含边缘的节点）。即，我们现在在G中拥有最大流量，现在添加/删除与之相关的节点和边缘，我不想为新图重新计算最大流量，实际上，我希望利用先前可用的结果来处理这个图形。

适当的预处理不会消耗太多时间/内存。

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

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

此外，对于删除节点，上述想法也行不通。

同时我的问题与另一个问题没有关联，该问题涉及动态添加/删除边缘。

@KeithRandall，我的问题是关于添加和删除顶点的，但那个问题是关于边的，实际上，对于一个顶点，你可能会添加n条边，所以顶点的情况比边的情况更复杂，例如，我对边有一些直觉，但对于顶点，我最好的解决方案并不好。 - Saeed Amiri
@Charles，你能描述一下为什么删除了max-flow标签吗？我在SO上添加了这个标签，因为它很有用，特别是在搜索时。 - Saeed Amiri
边缘是最重要的，添加或删除没有边缘的顶点是微不足道的。所以也许你正在询问是否有一种更有效的增量算法来添加连接到单个顶点的n条边，而不是运行链接的增量边缘算法n次？ - Keith Randall
@Saeed，术语“最大流”对外行人来说是通用且不明确的。也许考虑添加标签wiki，选择更精确的标签名称（也许是“maximum-flow”而不仅仅是“max-flow”？），并查看其他在SO上的问题，并在相关的地方添加它。采取这些步骤将阻止像我这样的新标签删除者在未来删除它。 - Charles
@Charles，我认为如果你希望别人这么做，你应该在编辑中提到，否则没有人能想到你的想法。此外，创建新标签并没有那么复杂的规则。程序员们知道这个概念叫做最大流，如果你看他们的代码，我敢肯定他们的函数名称中有很多是max_flow、MaxFlow、maxFlow等，而不是maximumFlow。 - Saeed Amiri
显示剩余2条评论
3个回答
1

添加顶点v时，使用旧流f并计算剩余图，然后通过DFS OutDeg(v)次获得增广路径。

要删除顶点v-计算所有离开v的流量，假设离开v的流量总和为a，则在(a>0)的情况下从s到t找到一条经过v的路径P，并将f(P)从流中减去并从a中减去。

我认为这应该有所帮助...我对添加比删除更有把握，所以我很想在评论中得到纠正：）

好的报价，但是你的添加顶点的方法在最坏情况下需要O(nE)的时间复杂度。另外，你的删除选项也需要O(nE)的时间复杂度。我认为这不是正确的方式，但是你的添加方式比我的更简单。 - Saeed Amiri
我认为你做不到比那更好了... 你确定有更好的方法吗？请注意，在大多数图中，outdeg(v) 不太可能很高，因此它的平均情况应该在 O(E) 中运行... - Ofek Ron
平均而言，平均度数不应该是O(E)，对于新顶点，平均度数应该在n/2左右（使用随机图）。但目前我认为你的算法有一些错误，它并不是本质上使用degree(v)时间计算，可能我们需要更多的时间（在遍历一个新添加的边超过一次的情况下）。此外，我认为没有直接的算法，但可以在这里询问是否有人有好的想法？ - Saeed Amiri
你是正确的，更准确地说，复杂度将为O(delta*E)，其中delta是f'-f的差异，其中f'是结束流量。假设我们得到了一个整数流量。 - Ofek Ron
我有十进制数而不是整数，但你建议的 O 不是很紧密但也不错 :) - Saeed Amiri
0
动态添加一个顶点 v 和其关联的边 E：
1）将 v 添加到图中。由于它没有边，因此不会影响最大流。
2）使用 this question 中的算法逐个将关联的边 E 添加到图中。
删除一个顶点及其关联的边时，请执行相反的操作。
1
你知道那个算法的顺序吗？每条边的复杂度超过O(E)，实际上并不好（我的算法更简单更快），而且你提供的方法也没有涵盖节点删除。 - Saeed Amiri
0

我在CSTheory.StackExchange上提出了这个问题，对于添加节点，我与其他人讨论后发现重新计算比其他已知算法更快，因为重新计算运行在半稀疏图（剩余图）上，所以足够快。对于删除节点，有一个很好的答案，将要删除的节点分成两个集合v_in和v_out，并在剩余图中从v_in到v_out计算流量，然后再通过在源和目标之间添加无限边，在剩余图中从v_in到v_out再次计算流量（最后比较它们的差异并更新剩余图）。 您可以在动态图中的增量最大流中查看相关的问答和讨论。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接