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].

Exercises 23.2-8

The algorithm fails on G=(V,E), V={1,2,3,4}, E={(1,2),(1,3),(2,4),(3,4)} which weight is {1,2,3,4}. If = {1,2}, = {3,4}, the minimum spanning tree of {3,4} is edge (3,4) which is not in minimum spanning of G.

Exercises 23.2-7

Let node u be the new vertex, and E’ be the incident edges. The minimum spanning tree for G=(V+u, T+E’) is the solution. Since T+E’ is O(V), using the Prim’s algorithm with Fibonacci heap, it can be done in O(V lgV) time.

Exercises 23.2-6

Kruskal algorithm is faster, since we can use the bucket sort.

Exercises 23.2-5

If the weight is bounded by W, we can use the array to implement priority queue. Hence the EXTRACT-MIN can be done in O(W)=O(1) time. Then the total running time is O(E).

If the weight is bounded by V, this situation is complicated. Using van Emde Boas data structure, or redistributive heap may help.

Exercises 23.2-4

O(Eα(V)), since we can sort in linear time.

Exercises 23.2-3

	E=Θ(V)	E=
Binary Heap	V lgV
Fibonacci Heap	V lgV