Describe a linear time algorithm for this does di-graph g

Assignment Help Engineering Mathematics

Reference no: EM132141240

Question :

Suppose that G is a directed graph. In class we discussed an algorithm that will determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem).

Consider the following similar problem: given graph G, is there any node in G that can reach every other node in G?

Such a node is called a "source node". We want to know whether any node of G is a source node. A trivial algorithm for this is to execute DFS n times, using each node in G as the start node of the DFS. But the total time for this algorithm is O( n* (n+m)).

Describe a linear time algorithm for this "does di-graph G have a source node problem".

Reference no: EM132141240

Questions Cloud

Design an algorithm to update the minimum spanning tre : Design an algorithm to update the minimum spanning tree when the weight of a single edge e is increased.

What speedup is possible with pipelining : What is the maximum execution rate without pipelining? What speedup is possible with pipelining?

Would there be any advantages to using the cts and rts frame : Suppose the IEEE 802.11 RTS and CTS frames were as long as the standard DATA and ACK frames.

How does the behavior of dbscan and k-means differ on : Suppose you are given two sets of 100 points that fall within the unit square. One set of points (a) is arranged so that the points are uniformly spaced.

Describe a linear time algorithm for this does di-graph g : Determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem).

Find a shortest path from s to t : Design an algorithm that given any two vertices s and t of G, find a shortest path from s to t using O(|E|) time.

Write an algorithm to determine the two closest cities : Suppose you are given a set of cities (p number of cities) and there longitude and latitude coordinates. You need to determine the two closest cities.

Determine the expected number of die rolls until a coin flip : Explain how to use die rolls to generate unbiased coin flips, and determine the expected number of die rolls until a coin flip is generated.

Write an algorithm to transfer all elements : Write an algorithm to transfer all elements from S to T so that the top of S is the first to be inserted onto T, and the bottom of S ends up at the top of T.

User Account

All Pages