Splay Trees:FIFO: Dynamic Tree Implementation

FIFO: Dynamic Tree Implementation

Time for non-saturating push is reduced by performing a succession of pushes along a single path in one operation. After a non-saturating push, the edge continues to be admissible, and we know its residual capacity. [6]

Initially each vertex is made into a one vertex node. Arc of dynamic trees are a subset of admissible arcs. Value of an arc is its admissible capacity (if (u,parent(u)) is an arc, value of arc will be stored at u). Each active vertex is a tree root.

Vertices will be kept in a queue as in FIFO algorithm, but instead of discharge(v), Tree- Push(v), will be used. We will further ensure that tree size does not exceed k (k is a parameter to be chosen later). The Tree-Push procedure is as follows:

Tree-Push(v)

4. But, if arc(v, w) is not admissible, replace (v, w), as current edge by next edge on v’s list. If v has no next-edge, then make the first edge, the current edge and cut-off all children of v, and relabel(v).

Analysis

1. Total time for relabeling is O(nm).

2. Only admissible edges are present in the tree, and hence if an edge (u, v) is cut in step (3) or in step (4) then it must be admissible, i.e., d(u) = d(v) + 1. Edge (v, u) can become admissible and get cut, iff, dthen(v) = dthen(u)+ 1 ≥ d(u)+ 1 = d(v) + 2. Thus, the edge gets cut again only if label increases by 2. Thus, for each edge, number of times it can get cut is O(n). So total number of cuts are O(nm).

3. As initially, there are at most n-single node trees, number of links are at most n+#no of cuts= n + O(nm) = O(nm).

Moreover, there is at most one tree operation for each relabeling, cut or link. Further, for each item in queue, one operation is performed. Thus,

LEMMA 12.2 The time taken by the algorithm is O(log k × (nm + #No of times an item is added to the queue))

Root-Nodes Let Tv denote the tree containing node v. Let r be a tree root whose excess has become positive. It can become positive either due to:

1. push from a non-root vertex w in Step 3 of the tree-push algorithm.

2.  push from a root w in Step 2 /* find size(w)+find size(r) >k */

REMARK 12.7 Push in Step 3 is accompanied by a cut (unless first push is non- saturating). As the number of cuts is O(nm), number of times Step 3 (when first push is saturating) can occur is O(nm). Thus, we need to consider only the times when first push was non-saturating, and the excess has moved to the root as far as push in Step 3 is concerned.

In either case let i be the pass in which this happens (i.e., w was added to the queue in pass (i − 1)). Let I be the interval from beginning of pass (i − 1) to the time when e(r) becomes positive.

Case 1: (Tw changes during I) Tw can change either due to link or cut. But number of times a link or a cut can occur is O(nm). Thus, this case occurs at most O(nm) time. Thus, we may assume that Tw does not change during interval I. Vertex w is added to the queue either because of relabeling of w, or because of a push in Step 2 from (say) a root v to w.

Case 2: (w is added because of relabeling) Number of relabeling steps are O(n2).

Thus number of times this case occurs is O(n2). Thus, we may assume that w was added to queue because of push from root v to w in Step 2.

Case 3: (push from w was saturating) As the number of saturating pushes is O(nm), this case occurs O(nm) times. Thus we may assume that push from w was non-saturating.

Case 4: (edge (v, w) was not the current edge at beginning of pass (i − 1)). Edge (v, w) will become the current edge, only because either the previous current edge (v, x) got saturated, or because of relabel(v), or relabel(x). Note, that if entire excess out of v was moved, then (v, w) will remain the current edge.

As number of saturating pushes are O(nm) and number of relabeling are O(n2), this case can occur at most O(nm) times. Thus, we may assume that (v, w) was the current edge at beginning of pass (i − 1).

Case 5: (Tv changes during interval I) Tv can change either due to link or cut. But the number of times a link or a cut can occur is O(nm). Thus, this case occurs at most O(nm) time. Thus, we may assume that Tv has not changed during interval I.

Remaining Case: Vertex w was added to the queue because of a non-saturating push from v to w in Step 2 and (v, w) is still the current edge of v. Moreover, Tv and Tw do not change during the interval I.

A tree at beginning of pass (i − 1) can participate in only one pair (Tw, Tv ) as Tw , because this push was responsible for adding w to the queue. Observe that vertex w is uniquely determined by r.

And, a tree at beginning of pass (i − 1) can participate in only one pair (Tw, Tv ) as Tv , because (v, w) was the current edge out of root v, at beginning of pass (i − 1) (and is still the current edge). Thus, choice of Tv will uniquely determine Tw (and conversely).

Thus, as a tree Tx can participate once in a pair as Tv , and once as Tw, and the two trees are unchanged, we have ),(v,w) |Tv | + |Tw|≤ 2n (a vertex is in at most one tree). As push from v to w was in Step 2, find size(v)+find size(w) > k, or |Tv | + |Tw| > k. Thus, the number of such pairs is at most 2n/k.

But from Fact 12.8, as there are at most O(n2) passes, the number of such pairs are O(n3/k).

Non-Root-Nodes Let us count the number of times a non-root can have its excess made positive. Its excess can only be made positive as a result of push in Step 2. As the number of saturating pushes is O(nm), clearly, O(nm) pushes in Step 2 are saturating.

If the push is non-saturating, then entire excess at that node is moved out, hence it can happen only once after a vertex is removed from Queue. If v was not a root when it was added to the queue, then it has now become a root only because of a cut. But number of cuts is O(nm). Thus, we only need to consider the case when v was a root when it was added to the queue. The root was not earlier in queue, because either its excess was then zero, or because its distance label was low. Thus, now either 1. distance label has gone up— this can happen at most O(n2) times, or 2. now its excess has become positive. This by previous case can happen at most O(nm + (n3/k)) times.

Summary If k is chosen such that nm = n3/k, or k = n2/m, time taken by the algorithm is O(nm log(n2/m)).