Question
a.
O (E∗f)
b.
O (E^2∗f)
c.
O (E∗f^2)
d.
O (E^2∗f^2)
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?
View solution
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
View solution
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:
View solution
Q. The equivalence of
¬ ∃x Q(x) is:
View solution
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)
View solution
Q. Which of the relations on {0, 1, 2, 3} is an equivalence relation?
View solution
Q. Which of the following is an equivalence relation on the set of all functions from Z to Z?
View solution
Q. Which of the following statements is true?
View solution
Q. If the time is now 4 O'clock, what will be the time after 101 hours from now?
View solution
Q. Let m = (313)4 and n = (322)4. Find the base 4 expansion of m + n.
View solution
Q. How many distinguishable permutations of the letters in the word BANANA are there?
View solution
Q. Let P and Q be two propositions, ⌐(P ↔ Q) is equivalent to:
View solution
Q. Negation of the proposition Ǝ x H(x) is:
View solution
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:
View solution
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:
View solution
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 :
View solution
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.
View solution
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 :
View solution
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 :
View solution
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 :
View solution
Suggested Topics
Are you eager to expand your knowledge beyond Discrete Structures? We've curated a selection of related categories that you might find intriguing.
Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!