[Solved] The time taken to compute the transitive closure of a graph is Theta(n2).

Computer Science Engineering (CSE)
Design and Analysis of Algorithms
The time taken to compute the transitive...

Q.	The time taken to compute the transitive closure of a graph is Theta(n2).
A.	true
B.	false
Answer» B. false
Explanation: the time taken to compute the transitive closure of a graph is theta(n3).

View all MCQs in: Design and Analysis of Algorithms

Discussion

Related Questions

A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
Consider a complete graph G with 4 vertices. The graph G has spanning trees.
Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?
If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.
Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
A graph is found to be 2 colorable. What can be said about that graph?
What is the chromatic number of compliment of line graph of bipartite graph?
What is the clique size of the line graph of bipartite graph?
Every Perfect graph has forbidden graph characterization.
Which graph is used to define the claw free graph?