It is Game Day and all roads lead to Cameron! The university has identified a se

Question

It is Game Day and all roads lead to Cameron! The university has identified a set of roads that get congested leading up to the game and wants to set up traffic monitors at intersections to ensure the smooth flow of traffic on these roads. A monitor placed at an intersection can monitor traffic flow on all the roads meeting at the intersection. Your prowess in computer science lands you the job of deciding the minimal number of monitors needed to ensure that all roads are monitored. (You can assume that every road connects two intersections with no intersection in between.) This problem seems difficult at first glance, but then you observe that the network of roads that need to be monitored is acyclic! Can you now come up with a linear-time algorithm to solve the problem? (Don’t worry about reporting where the monitors need to be placed.)

Explanation / Answer

er vertices be monitors

Let G=(vertices,edges) be a simple directed acyclic graph.

For all pair of vertices vert,x im vert, we can say vert is reachable from x if there is a directed path from x to vert in G

(let us assume that every vertex is reachable from itself)

for any vertex vert in vertices,let R(vert) be the reachablity number of vertex vert,which number of verices u in vert,that are reachable vert.

so the algorithm for a given DAG ,G=(vertices,edge),computes the values of R(vert) for all vertices vert.

so while providing analysis of algorithm as big-oh(n+m) time.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.