algorithm - 网络流是伪多项式时间吗？

Question

我们知道正常的背包问题具有伪多项式时间，因为 O(nW) 的运行时间。我想知道网络流的运行时间是否是伪多项式时间，因为使用 Ford-Fulkerson 算法的网络流的运行时间是 O(Cm)(m 表示边数，C 表示从起点离开的边的容量总和) ?

Answer 1

是的，Ford-Fulkerson 算法是一种伪多项式时间算法。它的运行时间为 O(Cm)，其中 C 是离开起始节点的容量之和。由于写出数字 C 需要 O(log C) 位，因此此运行时确实是伪多项式，但实际上不是多项式。

但是，对于最大流量确实存在强多项式时间算法，例如在时间 O(n ³ ) 中运行的 push-relabel 算法。

希望这可以帮助！