Problem 25 « Exercise Lover

July 1, 2007

Problems 25-2

Filed under: Problem 25 — yuhanlyu @ 1:15 pm

(a) Insert = $O(\log_d n)$ , Extract-Min = $O(d \log_d n)$ , Decrease-Key = $O(\log_d n)$ . If d = $\Theta(n^{\alpha})$ , the Insert and Decrease -Key will become $O(\frac{1}{\alpha})$ and Extract-Min will become $O(\frac{n^\alpha}{\alpha})$ .

(b) Let d = $\Theta(|V|^{\epsilon})$ , the complexity will become O(|E|).

Problems 25-1

Filed under: Problem 25 — yuhanlyu @ 1:14 pm

a. Let the new added edge be (u,v). If there are nodes u,v such that i is transitive to u, v is transitive to j. Then i is transitive to j in the G*.

b. Let G be one directed path start from u and stops in v. If we add edge (v,u), then all nodes in the graph are transitive to each other.

c. If i is transitive to v, then add edge (u,v) is no help to i and j. We can check this condition explicitly. Although there are $O(|V|^2)$ possible insert edges, but the situations which meet i is transitive to u and i is not transitive to v are only $O(|V|^2)$ possibilities. Hence, we can insert $O(|V|^2)$ edges in $O(|V|^3)$ time.