Splay Trees:Implementation Without Linking and Cutting Trees

Implementation Without Linking and Cutting Trees

Each vertex will have a list of edges incident at it. It also has a pointer to current edge (candidate for pushing flow out of that node). Each edge (u, v) will have three values associated with it c(u, v), c(v, u) and g(u, v).

Push/Relabel(v)

Here we assume that v is an active vertex and (v, w) is current edge of v.

Discharge(v)

Keep on applying Push/Relabel(v) until either

1. entire excess at v is pushed out, OR,

2. label(v) increases.

FIFO/Queue

Initialize a queue “Queue” to contain s.

Let v be the vertex in front of Queue. Discharge(v), if a push causes excess of a vertex w to become non-zero, add w to the rear of the Queue.

Let phase 1, consist of discharge operations applied to vertices added to the queue by initialization of pre-flow.

Phase (i + 1) consists of discharge operations applied to vertices added to the queue during phase i.

Let Φ = max{d(v)|v is active }, with maximum as zero, if there are no active vertices. If in a phase, no relabeling is done, then the excess of all vertices which were in the queue has been moved. If v is any vertex which was in the queue, then excess has been moved to a node w, with d(w) = d(v) − 1. Thus, max{d(w)|w has now become active}≤ max{d(v) − 1|v was active } = Φ − 1.

Thus, if in a phase, no relabeling is done, Φ decreases by at least one. Moreover, as number of relabeling steps are bounded by 2n2, number of passes in which relabeling takes place is at most 2n2.

Only way in which Φ can increase is by relabeling. Since the maximum value of a label of any active vertex is n − 1, and as a label never decreases, the total of all increases in Φ is (n − 1)2.

As Φ decreases by at least one in a pass in which there is no relabeling, number of passes in which there is no relabeling is (n − 1)2 + 2n2 ≤ 3n2.

FACT 12.8 Number of passes in FIFO algorithm is O(n2).