5. Suppose we are given both an undirected graph G with weighted edges and a minimum...

5. Suppose we are given both an undirected graph G with weighted edges and
a minimum spanning tree T of G .
(a) Describe an algorithm to update the minimum spanning tree when the
weight of a single edge e is decreased.
(b) Describe an algorithm to update the minimum spanning tree when the
weight of a single edge e is increased.
In both cases, the input to your algorithm is the edge e and its new weight;
your algorithms should modify T so that it is still a minimum spanning tree.
[Hint: Consider the cases e ∈ T and e 6∈ T separately.]

Solutions

Expert Solution

Colby Messinger answered 5 months ago

Next > < Previous

Related Solutions

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each...

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each edge labeled from the set {0,1}. Describe and analyze the worst-case time complexity of an efficient algorithm to find any cycle consisting of edges whose labels alternate 0,1.

Given an undirected graph G=(V, E) with weights and a vertex , we ask for a...

Given an undirected graph G=(V, E) with weights and a vertex , we ask for a minimum weight spanning tree in G where is not a leaf (a leaf node has degree one). Can you solve this problem in polynomial time? Please write the proof.

You are given an undirected graph G = ( V, E ) in which the edge...

You are given an undirected graph G = ( V, E ) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight from 1 to W, where W is a constant (independent of the number of edges or vertices). Show that it is possible to compute the single-source shortest paths in such a graph in O(E+V) time.

Consider an undirected graph G that has n distinct vertices. Assume n≥3. How many distinct edges...

Consider an undirected graph G that has n distinct vertices. Assume n≥3. How many distinct edges will there be in any circuit for G that contains all the vertices in G? What is the maximum degree that any vertex in G can have? What is the maximum number of distinct edges G can have? What is the maximum number of distinct edges that G can have if G is disconnected?

Using C++: Create a function to search an undirected weighted graph and find the highest weighted...

Using C++: Create a function to search an undirected weighted graph and find the highest weighted edge between two specific values. This should include a class declaration and the definition for all required members that are needed to support the search. NO NEED to code those members. You can assume any other data structures such as stack, heap, or linked list is defined (so you can use their standard functions without declaring or defining them).

Design a linear-time algorithm which, given an undirected graph G and a particular edge e in...

Design a linear-time algorithm which, given an undirected graph G and a particular edge e in it, determines whether G has a cycle containing e. Your algorithm should also return the length (number of edges) of the shortest cycle containing e, if one exists. Just give the algorithm, no proofs are necessary. Hint: you can use BFS to solve this.

Question 1: Given a graph with length l(e) on edges, find a minimum length paths from...

Question 1: Given a graph with length l(e) on edges, find a minimum length paths from a vertex s to V −s so that among all shortest lengths paths from s to V −s we find the ones with minimum number of edges. Use Dijkstra's algorithm

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph...

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, then your algorithm should output one. (It should not output all cycles in the graph, just one of them.) The running time of your algorithm should be O(m + n) for a graph with n nodes and m edges.

You are given a directed graph G(V,E) with n vertices and m edges. Let S be...

You are given a directed graph G(V,E) with n vertices and m edges. Let S be the subset of vertices in G that are able to reach some cycle in G. Design an O(n + m) time algorithm to compute the set S. You can assume that G is given to you in the adjacency-list representation.

give an example of a simple, undirected, weighted graph such that breadth-firstsearch outputs a search-tree that...

give an example of a simple, undirected, weighted graph such that breadth-firstsearch outputs a search-tree that is not a single source shortest path tree. Youranswer must (a) Specify the graphG= (V, E)by specifyingVandE. (b) Specify the weight functionw. (c) Specify an ordering of the vertices and the search-tree output by breadth-first search assuming the specified graph and ordering. (d) Specify a valid single-source shortest path treeT= (V, ET)by specifyingETand its root, the first vertex in your specified ordering. (e) Include...

Subjects