Bottleneck Spanning Tree (BST) Problem: Let T be any spanning tree of a given weighted connected...

 

Transcribed Image Text:

Bottleneck Spanning Tree (BST) Problem: Let T be any spanning tree of a given weighted connected undirected graph G. The bottleneck value of T is defined to be the maximum edge weight among edges of T. We say T is a bottleneck spanning tree (BST) of G if bottleneck value of T is minimum among all spanning trees of G. The Bottleneck Spanning Tree Problem is to compute a BST of G. (a) Show a graph G with two of its bottleneck spanning trees such that only one of them is a minimum spanning tree. (b) Show that any minimum spanning tree is always a bottleneck spanning tree. [This shows that finding a bottleneck spanning tree is no harder than finding a minimum spanning tree. In the remaining parts, we will show that one can be found in linear time.] (c) Give a linear-time algorithm that, given a graph G and a real number b, determines whether bottleneck value of a BST of G is at most b. (Note: no BST of G is given.) [Hint: consider the edges of G that have weight at most b. Do they contain a spanning tree?] (d) Use your algorithm for part (c) as a subroutine to design a linear-time algorithm for the Bottleneck Spanning Tree Problem. [Hint: use prune-&-search and the hint for part (c)] Bottleneck Spanning Tree (BST) Problem: Let T be any spanning tree of a given weighted connected undirected graph G. The bottleneck value of T is defined to be the maximum edge weight among edges of T. We say T is a bottleneck spanning tree (BST) of G if bottleneck value of T is minimum among all spanning trees of G. The Bottleneck Spanning Tree Problem is to compute a BST of G. (a) Show a graph G with two of its bottleneck spanning trees such that only one of them is a minimum spanning tree. (b) Show that any minimum spanning tree is always a bottleneck spanning tree. [This shows that finding a bottleneck spanning tree is no harder than finding a minimum spanning tree. In the remaining parts, we will show that one can be found in linear time.] (c) Give a linear-time algorithm that, given a graph G and a real number b, determines whether bottleneck value of a BST of G is at most b. (Note: no BST of G is given.) [Hint: consider the edges of G that have weight at most b. Do they contain a spanning tree?] (d) Use your algorithm for part (c) as a subroutine to design a linear-time algorithm for the Bottleneck Spanning Tree Problem. [Hint: use prune-&-search and the hint for part (c)]

Answer rating: 100% (QA)

aFor a graph G we have following possible spanning trees Out of these th... View the full answer