Consider a scenario where you have a set of n players in a multiplayer game that we
Question:
Consider a scenario where you have a set of n players in a multiplayer game that we would like to connect to form a team. You are given a connected, weighted, undirected graph, G, with n vertices and m edges, which represents the n players and the m possible connections that can be made to link them together in a communicating team (that is, a connected subgraph of G). In this case, the weight on each edge, e, in G is an integer in the range [1, n2], which represents the amount of game points required to use the edge e for communication. Describe how to find a minimum spanning tree for G and thereby form this team with minimum cost, using an algorithm that runs in O(m α(n)) time, where α(n) is the slow-growing inverse of the Ackermann function.
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia