adplus-dvertising
frame-decoration

Question

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^2∗f)

c.

O (E∗f^2)

d.

O (E^2∗f^2)

Answer: (a).O (E∗f)

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. 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:

Similar Questions

Discover Related MCQs

Q. Which of the following statements is false about convex minimization problem?

Q. The following LPP
Maximize z = 100x1+2x2+5x3
Subject to

14x1+x2−6x3+3x4 = 7
32x1+x2−12x3 ≤ 10
3x1−x2−x3 ≤ 0
x1, x2, x3, x4 ≥ 0

has

Q. Digital data received from a sensor can fill up 0 to 32 buffers. Let the sample space be S={0, 1, 2, .........., 32} where the sample j denote that j of the buffers are full and
p(i) =1/561 (33 - i). Let A denote the event that the even number of buffers are full. Then p(A) is:

Q. The equivalence of

¬ ∃x Q(x) is:

Q. Match the following in List - I and List - II, for a function f:

List - I
(a) ∀x ∀y (f (x)=f (y) → x=y)
(b) ∀y ∃ x (f (x)=y)
(c) ∀x f (x)=k

List - II
(i) Constant
(ii) Injective
(iii) Surjective

Code:
(a) (b) (c)

Q. Which of the relations on {0, 1, 2, 3} is an equivalence relation?

Q. Which of the following is an equivalence relation on the set of all functions from Z to Z?

Q. Which of the following statements is true?

Q. If the time is now 4 O'clock, what will be the time after 101 hours from now?

Q. Let m = (313)4 and n = (322)4. Find the base 4 expansion of m + n.

Q. How many distinguishable permutations of the letters in the word BANANA are there?

Q. Let P and Q be two propositions, ⌐(P ↔ Q) is equivalent to:

Q. Negation of the proposition Ǝ x H(x) is:

Q. Consider the following two sequences :

X = <B, C, D, C, A, B, C>
and Y = <C, A, D, B, C, B>

The length of longest common subsequence of X and Y is:

Q. A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of:

Q. An undirected graph G (V, E) contains n (n > 2) nodes named v1, v2,...,vn. Two nodes vi and vj are connected if and only if 0 < | i – j | ≤ 2. Each edge (vi, vj) is assigned a weight i+j.
The cost of the minimum spanning tree of such a graph with 10 nodes is :

Q. Which of the following is a valid reason for causing degeneracy in a transportation problem? Here m is no. of rows and n is no. of columns in transportation table.

Q. Consider the following LPP :

Max Z=15x1+10x2
Subject to the constraints
4x1+6x2 ≤ 360
3x1+0x2 ≤ 180
0x1+5x2 ≤ 200
x1, x2 ≥ 0

The solution of the LPP using Graphical solution technique is :

Q. Consider the following LPP :

Min Z=2x1+x2+3x3
Subject to :
x1−2x2+x3 ≥ 4
2x1+x2+x3 ≤ 8
x1−x3 ≥ 0
x1, x2, x3 ≥ 0

The solution of this LPP using Dual Simplex Method is :

Q. Consider a single perceptron with sign activation function. The perceptron is represented by weight vector [0.4 −0.3 0.1]^t and a bias θ=0. If the input vector to the perceptron is X=[0.2 0.6 0.5] then the output of the perceptron is :