Question 11 : What does Maximum flow problem involve?
1. finding a flow between source and sink that is maximum
2. finding a flow between source and sink that is minimum
3. finding the shortest path between source and sink
4. computing a minimum spanning tree
5.
View Answer   Discuss with Members

Question 12 : In what time can an augmented path be found?
1. O(|E| log |V|)
2. O(|E|)
3. O(|E|²)
4. O(|E|² log |V|)
View Answer   Discuss with Members

Question 13 : Under what condition can a vertex combine and distribute flow in any manner?
1. It may violate edge capacities
2. It should maintain flow conservation
3. The vertex should be a source vertex
4. The vertex should be a sink vertex
View Answer   Discuss with Members

Question 14 : Dinic's algorithm runs faster than the Ford-Fulkerson algorithm.
1. true
2. false
3.
4.
View Answer   Discuss with Members

Question 15 : How many constraints does flow have?
1. one
2. three
3. two
4. four
View Answer   Discuss with Members

Question 16 : What is the source?
1. Vertex with no incoming edges
2. Vertex with no leaving edges
3. Centre vertex
4. Vertex with the least weight
View Answer   Discuss with Members

Question 17 : Which algorithm is used to solve a maximum flow problem?
1. Prim's algorithm
2. Kruskal's algorithm
3. Dijkstra's algorithm
4. Ford-Fulkerson algorithm
View Answer   Discuss with Members

Question 18 : What does Maximum flow problem involve?
1. finding a flow between source and sink that is maximum
2. finding a flow between source and sink that is minimum
3. finding the shortest path between source and sink
4. computing a minimum spanning tree
View Answer   Discuss with Members

Question 19 : Does Ford- Fulkerson algorithm use the idea of?
1. Naïve greedy algorithm approach
2. Residual graphs
3. Minimum cut
4. Minimum spanning tree
View Answer   Discuss with Members

Question 20 : What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?
1. O(|E|)
2. O(|E||V|)
3. O(|E|²|V|)
4. O(|E| log |V|)
View Answer   Discuss with Members