The Gateway to Computer Science Excellence

0 votes

City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at intersections with traffic lights so that any segment of road can be reached by at least one ambulance that does not have to pass through a traffic light to reach the scene of the accident. If we model the road network as a graph, where intersections with traffic lights are vertices and edges represent road segments between traffic lights, the graph-theoretic question to be answered is:

- Find a spanning tree with minimum number of edges.
- Find a spanning tree with minimum cost.
- Find a minimal coloring.
- Find a minimum size vertex cover.

+1 vote

If we imagine city with proper block then graph will be somewhat like n*m grid with intersection point as vertex.

So we have to find an vertex where absence of ambulance would cause problem. This is similary to finding minimum number of vertex such that each edge is covered.

Hence answer would be finding vertex cover.

So we have to find an vertex where absence of ambulance would cause problem. This is similary to finding minimum number of vertex such that each edge is covered.

Hence answer would be finding vertex cover.

52,218 questions

59,890 answers

201,084 comments

118,128 users