You have an army of n robots at your disposal that you can program to collective

Question

You have an army of n robots at your disposal that you can program to collectively do various tasks. The robots use wireless communication to communicate with each other. Two robots are connected if they are within a distance d (range of wireless device) of each other. Thus, as the robots move around the territory, the robot network (graph) is changing. You want the robot network to stay connected while individual robots explore as much of the “territory" as possible. You have come up with the following rule: At any given time, each robot must be able to communicate with at least n/2 other robots. Given a graph G that is comprised of a vertex set V = {V1, V2, V3, V4, …, Vm} and edge set E = {E1, E2, E3, …, En} with weights {W1, W2, W3, …, Wn}, write an algorithm that determines at any point in time whether your rule is satisfied. What is the time complexity of the algorithm?

Explanation / Answer

Input: Vertex set V:{V1,V2,.....Vm}
       Edge set E:{E1,E2,E3,....En}
       Weights W:{W1,W2,......Wn}
       Number of edges n, range of the robots d
Output: True or False
Method:
Start
Construct m integers and assign one to each of the vertices
Let Bi be the integer representing ith vertex in V
for each edge Ei in E do
   if Ei connects Vi and Vj and Wi <= d
       add 1 to Bi and Bj
   end if
end for

Let O = true

for each Bi (1<= i <= m) do
   if Bi < n/2 then
       O = false
   end if
end for

return O

End

Time complexity of the algorithm is O(n) where n is the number of edges.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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