The Gateway to Computer Science Excellence
0 votes
147 views

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:

  1. Find a spanning tree with minimum number of edges.
  2. Find a spanning tree with minimum cost.
  3. Find a minimal coloring.
  4. Find a minimum size vertex cover.
in Graph Theory by Boss
edited by | 147 views

1 Answer

+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.
by Boss

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,890 answers
201,084 comments
118,128 users