4 Hostile Agents An intelligence service has n agents in a non-friendly country.

Question

4 Hostile Agents An intelligence service has n agents in a non-friendly country. Each agent knows some of the other agents and has in place procedures for arranging a rendezvous with anyone he or she knows. For each such possible rendezvous, say between agents i and j, any Pij. The government wants to transmit a confidential message among all the agents while maximizing the total probability that no message is intercepted. 1. Specify this problem as a graph optimization problem. 2. How do you structure your inputs to this problem? 3. Which algorithm do you use to solve it? 4. What is the computational efficiency of your chosen solution!

Explanation / Answer

1) The n agens can be considered as n nodes of a grapgh, and an edge (i, j) exists if there is possible rendezvous between agents i and j. And each edge is marked with weight pij. So now the problem becomes finding an edge set that can cover all vertices with minimum weight. This is nothing but minimum spanning tree problem.

2) The inputs to the problerm are the n- number of agents which will be the vertex set V, and E={(i, j), i, j have a possible rendezvous } and pij weight of each edge.

3) Since this is a minimum spanning tree problem, we can use prims or krushkals algorithm to solve this problem.

4) So the running time would be O( mlogn) where m is number of edges.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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