Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework 1

CS535

Due Date:  September 6th, 2023

CS Department, IIT

1.  Show that the following definitions of spanning tree are equivalent:

(a) A connected subgraph on n vertices with n − 1 edges.

(b) A connected subgraph with exactly one path between every pair of vertices.

2.  Prove the correctness of Boruvka/Sollin’s algorithm for MST.

3.  Suppose that all edge weights in a graph are integers in the range from 1 to  |V | .  How fast can you make Prim’s algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?

4.  Let us consider Boruvka/Sollin’s algorithm as shown in class.   Note that  Sollin’s algorithm selects several edges for inclusion in T at each stage.  It terminates when only one tree at the end of a stage or no edges to be selected.

(a)  Suppose that we run k phases of Algorithm 1, using the output G′  produced by one phase as the input G to the next phase and accumulating edges in T. Argue that the overall running time of the k phases is O(kE).

(b)  Suppose that after running k phases of Algorithm 1, as in part (4a), we run Prim’s algorithm by calling MST-PRIM(G′ , c′ , r), where G′ , with weight attribute c′ , is returned by the last phase and r is any vertex in G′ (V).  Show how to pick k so that the overall running time is O(Elg lgV). Argue that your choice of k minimizes the overall asymptotic running time.

(c)  For what values of |E| (in terms of |V |) does the above scheme asymptotically beat Prim’s algo- rithm without preprocessing?

5.  A bottleneck spanning tree T of an undirected graph G is a spanning tree of G whose largest edge weight is minimum over all spanning trees of G.  We say that the value of the bottleneck spanning tree is the weight of the maximum-weight edge in T.

(a)  Argue that a minimum spanning tree is a bottleneck spanning tree.

(b)  Give a linear-time algorithm that given a graph G and an integer b, determines whether the value of the bottleneck spanning tree is at most b.

(c)  Use  your  algorithm  for  part  (5b)  as  a  subroutine  to  design  a  linear-time  algorithm  for  the bottleneck-spanning-tree problem.