The cell phone company has developed an anti-virus that restores the original ring tone. To deliver the anti-virus to a cell phone, the company needs to call the phone; thus, they want to determine the customers that are infected so they can be called without disturbing the customers who are uninfected. The company has determined that a call between two cell phones is sufficient to transfer the virus from one phone to the other, regardless of which phone initiated the call. They have determined the phone that is the source of the initial infection as well as the time at which the original infection occurred. And they also have a list of length c (ordered by time of call) of all calls placed between cell phones during the time that the virus has been active.
You have been asked to help combat this virus. Design an algorithm to
find all the phones that the virus has reached starting from the initial
infection. The goal is to express your algorithm as a standard graph
algorithm. (There are other ways to solve the problem, but most of these
involve re-inventing an algorithm that is actually a standard graph
algorithm.) In other words, think about using the cell phone data to
construct a graph that you can feed to one or more of the algorithms in
Chapter 3. Be sure to describe how to interpret the output of any
such algorithm in terms of cell phones rather than in terms of graphs.
Also, be sure to note the runtime for your solution. (If you use a graph
algorithm from Chapter 3, you don't have to prove that it works since
this is done in the text.)