Problems 23-4

a. Correct, time is O(E lgE + E(V+E)).

b. incorrect

c. Correct, time is O(EV).

Problems 23-3

a. Suppose that the bottleneck spanning tree T is not minimum spanning tree T’. Let edge (u,v) be the heaviest edge in T’, (u,v) must not be in T. We can add (u,v) in T, and find a cycle that contains (u,v). The heaviest edge in this cycle is (u,v), it is impossible for minimum spanning tree to contain (u,v).

b. Eliminate all edges which weight greater than b and check whether graph is connected or not.

c. Using median finding algorithm to partition the edge set to two sets, one set has heavy weight edge. If the set with smaller cost can form a connected graph, then recursive on this edge set. Otherwise, find all connected component and contract all vertex in the same component into one vertex, then recursive on the heavy edge set. The time complexity is O(|E|).

Problems 23-2

http://www.cs.iitm.ernet.in/~tcslab/daa97page/probsol/solution3.ps

Problems 23-1

a. Let G=(V,E), V={1,2,3,4}, E={(1,2),(1,3),(1,4),(2,3),(2,4)}, weight is {1,3,4,2,5}. G has two second-best minimum spanning tree.

b.

c. For each node u, using BFS on the minimum spanning tree. When node v is visited, we can compute the maximum weight on the u,v-path easily.

d. We can find . Then replace  (u,v) by max[u,v].