Algorithm (MST, Prim's Algo, Kaskal's Algo)

Consider a connected, undirected, weighted graph G = (V, E, w), along with a single given hub node v V . A hub node is a vertex which has high degree, e.g., deg(v) |V |/2.

In general, an MST of G may contain an arbitrary number of edges which are incident to v. Instead, we want to find a minimum hub-independent spanning tree, defined as a spanning tree which uses at most two edges incident to v, and has weight less than or equal the weight of all other such spanning trees. Give an algorithm that solves this problem in O(E lg V + V 2 ) time.

1.. Give a pseudocode for an algorithm which takes a graph G and a hub vertex v and computes a minimum hub-independent spanning tree. Comment your code. If no such tree exists, your algorithm should return null.

2.. Find correctness of algorithm using the cycle and cut properties of an MST.