A phone company, RT&T;, has designed a network of n switching stations connected

Question

A phone company, RT&T;, has designed a network of n switching stations connected by m highspeed communication links. Each phone connects directly to one of the switching stations in his or her area. The engineers of RT&T; developed a prototype video chat system on the phone, but in order for it to have acceptable image quality, the number of links to transmit video cannot exceed 4. Design an efficient algorithm that computes, for each station, the set of stations it can link to for a video chat.

Explanation / Answer

Solution:
We can perform a modified DFS search, for each vertex (station), to find the stations
which can be reached by at most 4 edges (links) from the vertex. Just modify the DFS algorithm
as follows:

Algorithm ModDFS(G,v,depth,S)
Input: graph G, start 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
foreach edge in G.incidentEdges() do
tov G.opposite(edge,v)
if (! isVisited(tov)) then
S.insertLast(tov)
S ModDFS(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 new empty dictionary
foreach v in G.vertices() do
D.insert(v, ModDFS(G,v,4, a new sequence))

Given a graph in which every vertex is at most 4 edges away from any other, we would basically
be performing n complete DFS traversals. So the worst-case running time is O(n(n + m)). Note
that the running time is O(nm) if the network is connected (and thus m n 1).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.