question archive 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
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
Subject:Computer SciencePrice: Bought3
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 algorithm in O(E lg V + V 2 ) time.
1) Note that for some input graph G and hub vertex v, it may be impossible to construct a spanning tree using only two edges incident to v. Give example of such a graph and hub vertex.
2) Give example of a graph G and hub vertex v for which the spanning tree described above exists and is not an MST. Identify the minimum hub-independent spanning tree and an MST.
3) Let K5 be the complete graph on 5 vertices and v be a fixed vertex. Assign weights to this graph such that any minimum hub-independent spanning tree has exactly two edges incident on v.
4) What is a pseudocode for an algorithm which takes a graph G and a hub vertex v and computes a minimum hub-independent spanning tree. Comment the code. If no such tree exists, your algorithm should return null.
5) Correctness of algorithm using the cycle and cut properties of an MST.
