MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms November 5, 2001 Lecture 15 Lecturer: Michel X. Goernans Scribe: Timothy Danford Last time we saw that all the operations on dynamic trees are expressed in terms of expose, which was itself expressed in terms of splice and splay. We'll do the running time analysis of dynamic trees in a manner very similar to the way we did the analysis of splay trees. 1 Analysis of Dynamic Trees - We'll maintain a credit invariant, the rank of the node. S(X) = number of descendants of x in the virtual tree. = log,(s(x)) The credit invariant: every node maintains r(x) units of credit. - Now, let's look at splicing: -We switch a middle child with a left child, but this has no impact on the credit invariance. -Splicing occurs only at Step 2 of expose, and therefore can be charged to Step 3 of expose. (i.e., we charge the splicing of Step 2 to the splaying of Step 3). - Therefore, the cost of our expose operations is the cost of the splaying in Step 1and the cost of the splaying in Step 3 (everything else we said about splay trees also applies to virtual trees). 1.1 Splaying We showed that splay(v) had the amortized cost of 3(r (root) -r (v)) +1= O(1og n) since 0 < r(v) < log n for any v in a tree of size n. We can double this with no problem, so the amortized cost of expose(v) is O(1ogn). Therefore, any sequence of m expose operations has an amortized cost of O(m log n). This implies that the cost is O(m1ogn) + O(n1ogn) = O((m +n) logn). find-cost, find-root, find-min, add-cost: no change in the tree, so no change in the credit invariant. cut: adds an edge and removes another. Therefore, we gain relative to the credit invariant. link: we add a subtree. When we do this, we've exposed two vertices w and v, so they are the roots of their respective trees. Then when we link the two trees, the credit invariant increases by logn at only one node (i.e., at v if we're linking w to v) and by O(1ogn) overall. Bottom Line: Any sequence of m dynamic tree operations will take O((m +n) logn) time. 2 Using Dynamic Trees to implement Cancel & Tighten ef- ficiently - We have a directed graph G, a flow f,and a residual capacity uf. We want to repeatedly find cycles and push as much flow along those cycles as possible. Some of the edges of the graph will be maintained in the dynamic tree and for those we will maintain their residual capacity uf; for the edges not in the dynamic tree, we will maintain their actual flow. Thus, wheneveran edge is removed from the dynamic tree data structure, we need to compute its flow by subtracting the residual capacity uf from the capacity u; conversely when we add an edge to the tree. -We start with all the trees as singletons from the graph. -We always try to find an admissible arc entering the root of one of the (dynamic) trees. -If we find an admissible arc between two trees (and entering the root of one of them), we connect them with link. Observe that the resulting tree is still a tree directed away from its root. -If, on the other hand, the admissible arc connects a node to the root r of its tree, then we -have found a cycle to cancel consisting of the arc and the path from the root r to the other endpoint of the arc, -compute the amount S by which we can cancel the cycle (which is the minimum of the residual capcaities along the cycle), -increase the flow on the admissible arc by S (the arc is not added to the tree) -decrease the residual capacity by 6 along the path from root to the other endpoint of the arc (the call to addcost). -remove all the edges that have been saturated -When there are no admissible edges entering r, there are no more admissible cycles passing through r and we remove all the arcs in the tree leaving r. This means that for every arc (r,v) where v is a child of r in the tree, we compute its flow from its residual capacity and remove the arc from the tree; we then remove r from consideration my marking it. 2.1 Cancel & Tighten Algorithm, with Dynamic Trees VV : unmark(v), make -tree(v) while 3 unmarked v, do if 3 admissible arc (w,r) then -if findroot(w) # r then * link(w,r, uf(w,r)) -else * S = min(uf(w,r),findcost(findroot(w))) * f (w,4 +f(w, +6 * if f (w,r) = u (w,r), then (w,r) is inadmissible * addcost(w,-S) * while findcost(findmin(w))= 0 do . x tfindmin(w) f(parent(x),x) tu(parent(x),x) . cut(x) else (there are no admissible arcs (w,r)) -mark(r) -for each child x of v * f (r,X)=~(r,X)-findcost(x) * cut(x)2.2 Correctness & Running Time Correctness should be obvious, as should running time, which works out as follows: # of cancel/tighten steps 0(mn log n) 0(nlognC) 0(m2 n log n) ortime per cancel step O(m) 0(mn log nlognC)tighten step