An O(n3/log(n))-time maximum-flow algorithm

An O(n3/log(n))-time maximum-flow algorithm

0.00 Avg rating—0 Votes
Article ID: iaor19981321
Country: United States
Volume: 25
Issue: 6
Start Page Number: 1144
End Page Number: 1170
Publication Date: Jun 1996
Journal: SIAM Journal On Computing
Authors: , ,
Abstract:

We show that a maximum flow in a network with n vertices can be computed deterministically in O(n3/log(n)) time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of O(n3). The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs.

Reviews

Required fields are marked *. Your email address will not be published.