Let G = (V, E) be an undirected graph with a cost C 0 on each edge. You are give

ID: 3529837 • Letter: L

Question

Let G = (V, E) be an undirected graph with a cost C 0 on each edge. You are given a minimum spanning tree T in G. Now we are moving to a dynamic scenario: a new edge is added to G, connecting two nodes upsilon, omega V(G) with cost c. Give an efficient algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G (but not to T). Make your algorithm run in time O(|E|). Can you do it in O(|V|) time? Please mention what data structure are you assuming for representing the graph G and the tree T. Suppose T is no longer the minimum-cost spanning tree. Give a O(|E|-time algorithm to update the tree T to the new minimum spanning tree.

Explanation / Answer

Please rate with 5 stars :)

here is the solution:

We can do better than BFS for the shortest-path search if you store the tree the right way.

Say one node r in T is the root (you can pick any node and BFS from there to generate this structure if you have marked the tree edges in a matrix or adjacency-list graph structure), and each other node has a parent pointer and a depth count. To find the shortest path between a and b in T:

Proof of the validity of this algorithm is left as an exercise to the reader. This is O(|V|) like BFS, but will also generally be faster. Only a few MST configurations would actually require O(|V|) time in practice. Of course, generating the parent-link tree takes O(|V|) time to begin with, so this only help in some circumstances, such as if you use an MST-building algorithm that naturally creates this structure in the process of determining the MST.

As another commenter said, note that if there is a MST for a graph it is connected, so |V| <= |E| and thus O(|V|) < O(|E|).

Also, to fix the tree in O(|V|) time, if needed, simply find the longest edge on the cycle and remove it, replacing it with the new edge.

Navigate

Let G = (V, E) be an undirected graph where |V| = n and |E| = m. Suppose for two

Let G = (V, E) be an undirected, connected graph with n vertices and m edges. Al

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

Let G = (V, E) be an undirected graph with a cost C 0 on each edge. You are give

Question

Explanation / Answer

Related Questions

Navigate