Answered: 5.22. You are given a graph G = (V, E)…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Note, you are given the tree T and the edge e = (y, z) whose weight is changed; you are told its old weight w(e) and its new weight w~(e) (which you type in latex by widetilde{w}(e) surrounded by double dollar signs).

In each case specify if the tree might change. And if it might change then give an algorithm to find the weight of the possibly new MST (just return the weight or the MST, whatever's easier). You can use the algorithms from class (DFS, Explore, BFS, Dijkstra's, SCC, Topological Sort) as black-box algorithms if you'd like. Explain your algorithm in words. Note the running time of your algorithm in terms of n and m.

Part (a): e ∉ T and w~(e) > w(e):

[Blank space for the answer]

Part (b): e ∉ T and w~(e) < w(e):

[Blank space for the answer]

Part (c): e ∈ T and w~(e) < w(e):

[Blank space for the answer]

Part (d): e ∈ T and w~(e) > w(e):

[Blank space for the answer]

Note, you are given the tree T and the edge e = (y, z) whose weight is changed; you are told it's
old weight w(e) and it's new weight w(e) (which you type in latex by \widehat{w}(e) surrounded by
double dollar signs).
In each case specify if the tree might change. And if it might change then give an algorithm to find
the weight of the possibly new MST (just return the weight or the MST, whatever's easier). You can
use the algorithms from class (DFS, Explore, BFS, Dijkstra's, SCC, Topological Sort) as black-box
algorithms if you'd like. Explain your algorithm in words. Note the running time of your algorithm
in terms of n and m.
Part (a): e T and ŵ(e) > w(e):
Part (b): e T and w(e) < w(e):
Part (c): e E T and w(e) < w(e):
Part (d): e € T and ŵ(e) > w(e):

=
5.22. You are given a graph G (V, E) with positive edge weights, and a minimum spanning tree
T = (V, E') with respect to these weights; you may assume G and T are given as adjacency lists.
Now suppose the weight of a particular edge e ← E is modified from w(e) to a new value w(e). You
wish to quickly update the minimum spanning tree T to reflect this change, without recomputing
the entire tree from scratch. There are four cases. In each case give a linear-time algorithm for
updating the tree.
(a) e
E' and w(e) > w(e).
(b) e
E' and w(e) < w(e).
(c) e € E' and w(e) < w(e).
(d) e € E' and w(e) > w(e).

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions