Beyond the flow decomposition barrier

被引：15

作者：

Goldberg, AV ^{[1
]}

Rao, S ^{[1
]}

机构：

[1] NEC Res Inst, Princeton, NJ 08540 USA

来源：

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1997年

关键词：

D O I：

10.1109/SFCS.1997.646087

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We introduce a new approach to the maximum flow problem. This approach is based on assigning are lengths based on the residual flow value and the residual are capacities. Our approach leads to an O(min(n(2/3), m(1/2))m log(n(2)/m) log U) time bound for a network with n vertices, m arcs, and integral are capacities in the range [1,...,U]. This is a fundamental improvement over the previous time bounds. We also improve bounds for the Gomory-Hu tree problem, the parametric flow problem, and the approximate s-t cut problems.

引用

页码：2 / 11

页数：10