Hi,
For homework 3 question 2, you may assume the graph is connected (aka. k>0 and the algorithm can always find some edge to contract). Also, part 5 of that question should have "at most $O(|V|^{2\alpha})$" instead of $\Omega(|V|^{2\alpha})$.
Sorry about this.
Richard
Subscribe to:
Post Comments (Atom)
I suppose this also affects the second part of the question, i.e.
ReplyDeleteHow many times must we iterate the algorithm to be sure that it outputs a min-cut with probability at least 2/3?
So would this second question become a probability of at most 2/3? And wouldn't this be a silly question to ask then?