Imagine that you are a medical practitioner for a developing country, Strategia, and it is your job
Question:
Imagine that you are a medical practitioner for a developing country, Strategia, and it is your job to inoculate people in each village in Strategia so as to limit the ability of the Kissoba virus to spread in Strategia. The Kissoba virus can only be spread between two people if they kiss. For each village, you are given a kissing graph, G, whose vertices are the people in that village and whose edges are pairs of people who regularly kiss. Unfortunately, you don’t have an unlimited supply of the Kissoba vaccine, and each shot is expensive. So the president of Strategia has asked that you limit the people you vaccinate to those who are central kissers, where a central kisser is a person, p, such that there are no two people, r and q, who are kissed by p such that there is a sequence of kissing pairs of people that starts with r and leads to q while avoiding p. Given a graph, G, representing the kissing graph for a village in Strategia, describe an efficient algorithm for identifying all the central kissers in G, and analyze its running time.
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia