CODEWITHSUNDEEP
algorithmgraph-algorithmford-fulkerson
user3510049
user3510049

Reputation: 23

Running time analysis of Ford Fulkerson Algorithm that finds the maximum flow in a network

I know that the running time of ford fulkerson in general is O(f*(n+m)) where f* is the maximum flow of the network and the n , m are the number of vertices and edges in the network , however what if all edge capacities are bounded by a constant C, how will this affect the running time ?

or will it affect the running time ?

Upvotes: 1

Views: 3304

Answers (1)

amit
amit

Reputation: 178411

Assuming a simple graph, the given constraint basically means that no more than c*(n-1) leave the source. This means f* <= c*(n-1), and since c is constant, we can conclude that the running time with no modifications will now be O(n^2+nm).

Upvotes: 1

Related Questions