E is the number of edges in the graph and f is maximum flow in th
E is the number of edges in the graph and f is maximum flow in the graph. When the
capacities are integers, the runtime of Ford-Fulberson algorithm is bounded by:A. O (E∗f)
B. O (E<sup>2</sup>∗f)
C. O (E∗f<sup>2</sup>)
D. O (E<sup>2</sup>∗f<sup>2</sup>)
Please scroll down to see the correct answer and solution guide.
Right Answer is: A
SOLUTION
Concept:
In graph theory, a flow network is defined as a directed graph involving a source and sink and other nodes ,all connected with edges. Each edge has an individual capacity which is the maximum limit of flow that edge could allow.
Explanation:
Some conditions about flow:
1) Incoming flow and outgoing flow should be equal.
2) Flow should be between 0 and capacity of the edge.
3) Net flow follows skews symmetry i.e. F(u, v) = - F(v, u) where u and v are the vertices.
Ford Fulkerson algorithm:
1) Initially flow in all edges is 0
2) while there exists an augmenting path between source and sink, augment flow between source and sink along that path
3) Update the remaining graph
4) return
Augmenting path is a simple path from source to sink which do not include any cycle and pass through positive weighted edges. If, no augmenting path, then flow is maximum between source and sink.