Question

A company named RT&T has a network of n switching stations connected by m high-speed communication links. Each customer’s phone is directly 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 eachother 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 network is represented by a graph.

Design and give the pseudo-code for an efficient algorithm that computes, for each station, the set of stations it can reach using no more than 4 links. Analyze its running time.

Answer 1

A customized DFS search can be performed in this case for each vertex or station, to find the stations
reachable by at 4 or less links from the vertex. The DFS algorithm will be:

Algorithm CustDFS(G,v,depth,S)
Inputs: graph G, begin vertex v, depth to traverse to, S sequence to store the result in
Output: a sequence S of vertices reachable from v in at most depth hops
count ← 0
mark v as visited
if (depth = 0) then
return S
for each edge in G.incidentEdges() do
tov ← G.opposite(edge,v)
if (! isVisited(tov)) then
S.insertLast(tov)
S ← CustDFS(G,tov,depth − 1,S)
return S

Algorithm ComputeFourSets(G)
Input: a graph G
Output: a dictionary keyed on a vertex with values being sequences of nodes 4-reachable from that vertex
D is a blank dictionary
for each v in G.vertices() do
D.insert(v, CustDFS(G,v,4, a new sequence))

For a graph where every vertex is at most 4 edges away from others, n complete DFS traversals will be performed practically. So the worst-case run time is O(n(n + m)). But the running time is O(nm) if the network is connected (when m ≥ n − 1).

Hope this helps.