首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >全对最大流

问全对最大流
EN

Stack Overflow用户
提问于 2012-12-21 12:59:36
回答 2查看 3K关注 0票数 8

给定有向加权图,如何求出所有顶点对之间的最大流(或最小边切)。

天真的方法是简单地为每对调用一个像Dinic这样的最大流算法,其复杂性是O((V^2)*E)。

因此,对于所有对,它都是O((V^4)*E)。

是否可以通过一些优化来降低O((V^3)*E)或O(V^3)的复杂性?

EN

回答 2

Stack Overflow用户

发布于 2013-04-07 08:00:40

Gomory树不适用于有向图,抛开这一点,Gomory树将通过应用最小割集来形成图的最大流。

时间复杂性是:

代码语言:javascript
复制
O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2)

*使用最优最小切割算法(最大流切法)

这个示例演示了Gomory树是如何从给定的图构造的。

票数 4
EN

Stack Overflow用户

发布于 2014-06-21 01:13:25

Gomory树不适用于有向加权图。

与在有向图上运行n^2最大流相比,是否存在求解所有对最大流的算法是一个有待解决的问题。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/13990689

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档