question archive The Hormel agency is designing a spam distribution network
The Hormel agency is designing a spam distribution network
Subject:Computer SciencePrice: Bought3
The Hormel agency is designing a spam distribution network. The network is represented by a binary tree T = (V, E) with root re V and nonnegative edge-weight function w : E -> R. Each vertex v C V represents a server with one million email addresses, and each edge e E E represents a communication channel that costs w(e) dollars to purchase. A server v E V receives spam precisely if the entire path in T from the root r to v is purchased. The agency wants to send spam from root r to K servers including the root (K < |VD. by spending as little money as possible. The agency is seeking an algorithm that finds a minimum-weight connected subgraph of T with K vertices including the root. O a. This problem can be solved by K iterations of Prim's Minimum Spanning Tree algorithm starting from root r. O b. This problem is NP-complete and cannot be solved in polynomial time, unless P = NP. O c. This problem can be solved by K iterations of Dijkstra's Single Source Shortest Paths algorithm starting from root r. O d. This problem can be solved in polynomial time by dynamic programming. since OSSP holds on each subtree of T and each K'SK.
