所有配对最大流量 [英] All pair Maximum Flow

问题描述

给定一个有向加权图，如何找到所有顶点对之间的最大流量（或 Minimum Edge Cut ）。
简单的方法很简单调用像Dinic's这样的Max Flow流程算法，其复杂性为每对 O（（V ^ 2）* E）。 >
因此，对于所有的对，它是 O（（V ^ 4）* E）。

是否有可能将复杂度降至 O（（V ^ 3）* E）或< c $ c> O（V ^ 3）通过一些优化？

解决方案

Gomory-Hu Tree 不适用于有向图，将其放在一边，Gomory-Hu Tree将通过应用最小切割形成Graph最大流。 b b 复杂性是：
$ b $ pre $ O（| V | -1 * T（最小割））= O（| V | -1 * O（2 | V | -2））〜O（| V | ^ 2）


*使用最佳的最小限度算法（ Max-Flow Min-Cut Reduction ）

example 举例说明了Gomory-Hu Tree是如何从给定的Graph构造的

Given a directed weighted graph, how to find the Maximum Flow ( or Minimum Edge Cut ) between all pairs of vertices.
The naive approach is simply to call a Max Flow algorithm like Dinic's, whose complexity is O((V^2)*E), for each pair.
Hence for all pairs it is O((V^4)*E).

Is it possible to reduce the complexity to O((V^3)*E) or to O(V^3) by some optimizations?

解决方案

Gomory-Hu Tree does not work with directed graphs, putting that aside, Gomory-Hu Tree will form a Graph maximum flow by applying minimum cuts.

The time complexity is:

O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2)

* using an optimal minimum-cut algorithm (Max-Flow Min-Cut Reduction)

This example illustrate how Gomory-Hu Tree is constructed from a given Graph

这篇关于所有配对最大流量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！