In what time can an augmented path be found?(a) O(|E| log |V|)(b) O(|E|)(c) O(|E|^2)(d) O(|E|^2 log |V|)The question was posed to me during an interview.The origin of the question is Flow Networks in chapter Flow Networks of Data Structures & Algorithms II

In what time can an augmented path be found?(a) O(|E| log |V|)(b) O(|E

1.	In what time can an augmented path be found?(a) O(\|E\| log \|V\|)(b) O(\|E\|)(c) O(\|E\|^2)(d) O(\|E\|^2 log \|V\|)The question was posed to me during an interview.The origin of the question is Flow Networks in chapter Flow Networks of Data Structures & Algorithms II
Answer» Right choice is (B) O(\|E\|) The EXPLANATION is: An augmenting PATH can be found in O(\|E\|) mathematically by an unweighted shortest path ALGORITHM.

Discussion

No Comment Found

Related InterviewSolutions

How many constraints does flow have?(a) one(b) three(c) two(d) fourI have been asked this question by my school teacher while I was bunking the class.This key question is from Flow Networks in portion Flow Networks of Data Structures & Algorithms II
What is the running time of Dinic’s blocking flow algorithm?(a) O(V^2E)(b) O(VE^2)(c) O(V^3)(d) O(E max |f|)The question was asked in a national level competition.The query is from Flow Networks in division Flow Networks of Data Structures & Algorithms II
Who is the formulator of Maximum flow problem?(a) Lester R. Ford and Delbert R. Fulkerson(b) T.E. Harris and F.S. Ross(c) Y.A. Dinitz(d) KruskalThis question was addressed to me during an interview.My question is from Flow Networks topic in chapter Flow Networks of Data Structures & Algorithms II
What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?(a) O(|E|)(b) O(|E||V|)(c) O(|E|^2|V|)(d) O(|E| log |V|)I have been asked this question in unit test.My doubt stems from Flow Networks in division Flow Networks of Data Structures & Algorithms II
Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm.(a) true(b) falseThis question was posed to me in a national level competition.Query is from Flow Networks topic in section Flow Networks of Data Structures & Algorithms II
In what time can an augmented path be found?(a) O(|E| log |V|)(b) O(|E|)(c) O(|E|^2)(d) O(|E|^2 log |V|)The question was posed to me during an interview.The origin of the question is Flow Networks in chapter Flow Networks of Data Structures & Algorithms II
A simple acyclic path between source and sink which pass through only positive weighted edges is called?(a) augmenting path(b) critical path(c) residual path(d) maximum pathThis question was posed to me during an online exam.Question is from Flow Networks in section Flow Networks of Data Structures & Algorithms II
Find the maximum flow from the following graph.(a) 22(b) 17(c) 15(d) 20This question was addressed to me during an interview.This interesting question is from Flow Networks topic in portion Flow Networks of Data Structures & Algorithms II
Under what condition can a vertex combine and distribute flow in any manner?(a) It may violate edge capacities(b) It should maintain flow conservation(c) The vertex should be a source vertex(d) The vertex should be a sink vertexThe question was asked in class test.I'd like to ask this question from Flow Networks topic in portion Flow Networks of Data Structures & Algorithms II
The first step in the naïve greedy algorithm is?(a) analysing the zero flow(b) calculating the maximum flow using trial and error(c) adding flows with higher values(d) reversing flow if requiredThe question was asked during an online exam.I need to ask this question from Flow Networks in division Flow Networks of Data Structures & Algorithms II

In what time can an augmented path be found?(a) O(|E| log |V|)(b) O(|E|)(c) O(|E|^2)(d) O(|E|^2 log |V|)The question was posed to me during an interview.The origin of the question is Flow Networks in chapter Flow Networks of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment