An O(V
5/3
E
2/3) algorithm for the maximal flow problem |
| |
Authors: | Zvi Galil |
| |
Affiliation: | (1) Department of Mathematical Sciences, Computer Science Division, Tel-Aviv University, Ramat-Aviv, Tel-Aviv, Israel |
| |
Abstract: | Summary A new algorithm for finding a maximal flow in a given network is presented. The algorithm runs in time O(V
5/3
E
2/3), where V and E are the number of the vertices and edges in the network.
We use the notation A = 0(B) A = Ω(B)] for A ≦ cB A ≧ cB], and A = θ(B) for c
1
B≦A ≦ c
2
B where c, c
1and c
2are positive constants. (The same constants for all the occurrences of this notation) |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|