Search for question
Question

2. (a) A company named RT&T has a network of n stations connected by m high-speed communication links. Each customer's phone

is connected to one station in his or her area. The engineers of RT&T have developed a prototype video-phone system that allows

two customers to see each other during a phone call. In order to have acceptable image quality, however, the number of links used

to transmit video signals between the two parties cannot exceed 4. Suppose that RT&T's network is represented by a graph.

Design an efficient algorithm that computes, for each station, the set of stations it can reach using no more than 4 links.