4
$\begingroup$

This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea is to contract the graph, i.e. collapse two or more nodes into one node. So each reduction will reduce the graph by at least half nodes. The question is to come up with implementation such that time complexity of MST-REDUCE is $O(E)$. This uses set operations. MakeSet, Union and Find-Set. I've annotated my analysis in the picture along with algorithm. I'm thinking to implement the set as linked list here. So my make-set and find-set are $O(1)$. But Union sucks: $O(V)$. Since we are doing union for all the elements, we have total $O(V^2)$ time spent in union. Which gives amortized $O(V)$. Now the problem isn't clear whether it is expecting amortized time complexity or not. So I'm wondering if any better approach is possible. Note the algorithm is running for all nodes and all edges. Hence I think amortized makes sense.

Here is my analysis (line, complexity)

1-3 $V$

4-9 $\frac{V}{2} \cdot union = \frac{V}{2} \cdot \frac{V}{2} = V^2 = V$ (amortized)

10 $V \cdot findset = V$

12-21 $E \cdot findset = E$

Since $E >= V - 1$, we have overall time complexity of $O(E)$.

0   MST-REDUCE(G, orig, c T)
1   for each v in V[G]
2       mark[v] <- FALSE
3       MAKE-SET(v)
4   for each u in V[G]
5       if mark[u] = FALSE
6           choose v in Adj[u] such that c[u,v] is minimized.
7           UNION(u,v)
8           T <- T union { orig(u,v) }
9           mark[u] <- mark[v] <- TRUE
10  V[G'] <- { FIND-SET(v) : v in V[G] }
11  E[G'] <- { }
12  for each (x,y) in E[G]
13      u <- FIND-SET(x)
14      v <- FIND-SET(y)
15      if (u,v) doesn't belong E[G']
16          E[G'] <- E[G'] union {(u,v)}
17          orig'[u,v] <- orig[x,y]
18          c'[u,v] <- c[x,y]
19      else if c[x,y] < c'[u,v]
20          orig'[u,v] <- orig[x,y]
21          c'[u,v] <- c[x,y]
22  construct adjacency list Adj for G'
23  return G', orig', c', T
$\endgroup$
  • $\begingroup$ Please copy the algorithm (with your modification) in the question text. As for your analysis, the math seems doubtful (do you always mean to write $O(.)$?). Futhermore, the exercise suggests you have to modify the algorithm, but I can't see you have. And you don't use that the graph is sparse at all. So by these simple indicators, I don't think your solution is correct. $\endgroup$ – Raphael Aug 31 '12 at 7:36
  • $\begingroup$ @Raphael edited the question. Yes I mean O(). Yes you are right, I've not modified the algorithm as it is, but tried to optimize on the Disjoint Set which it was using. The idea is to use linked list representation of set as I mentioned. "Graph is sparse" is used in complexity approximation that E is almost equal to V. $\endgroup$ – Ankush Aug 31 '12 at 8:34
  • 2
    $\begingroup$ Thanks! There are much better UNION-FIND structures than linked lists, but those would not be "simple", I guess. I only see you use $E \geq V-1$ which is only a lower bound. You would have to use an upper bound on $E$ in terms of $V$. $\endgroup$ – Raphael Aug 31 '12 at 8:39
  • $\begingroup$ Good point. let me think about it. $\endgroup$ – Ankush Aug 31 '12 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.