Minimum cost spanning trees, We have a graph with node set (0,...,n-1) and we de

Question

Minimum cost spanning trees, We have a graph with node set (0,...,n-1) and we define the cost of edge (u,v) as (u-v) Estimate the time needed to compute a minimum cost spanning tree if you apply Prim's algorithm and Kruskal's algorithm.In that estimate, try to be as efficient as possible while using algorithms and data structure that were discussed in this course. In Particular, specify which variant of priority queue would you use, What sorting method etc. If your selection are not optimal but the analysis is correct you will get a partial score.

Explanation / Answer

Let the set c and c* be the sets output by APPROX-VERTEX-COVER and OPTIMAL-VERTEX-COVER respectively. Also, let A be the set of edges selected by line 4.

Because, we have added both vertices, we get c = 2|A| but OPTIMAL-VERTEX-COVER would have add one of two.

=>     c/c* p(n) = 2.

Formally, since no two edge in A are covered by the same vertex from c* (since, once an edge is picked in line 4, all other edges that are incident on its endpoints are deleted from E` in line 6) and we the lower bound:

            |c*| A        ---------------------------------- 1

On the size of an OPTIMAL-VERTEX-COVER.

In line 4, we picked both en points yielding an upper bound on the size of Vertex-Cover.

            |c| 2|A|

Since, upper bound is an exact in this case, we have

            |c| = 2|A|       ---------------------------------- 2
Take |c|/2 = |A| and put it in equation 1
         |c*| |c|/2
    |c*|/|c| 1/2
     |c*|/|c| 2 = p(n)

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---