Goldberg&Tarjan: How to find a blocking flow in a graph

Question

I want to implement the Goldberg & Rao algorithm for finding a maxflow in a graph. My problem is the update step where every paper and report is stating "In the resulting graph, find a blocking flow or a flow of value Delta." They all refer to Goldberg & Tarjan for finding a blocking flow. There are two things I don't understand:

1. How am I supposed to find a flow of value Delta?
2. But more important: how can I find a blocking flow?

Regarding questions 2: I read the two papers (the one by Goldberg & Tarjan "A New Approach to the Maximum-Flow Problem" and the one about dynamic trees - both were not that hard to understand). Every paper/report/book about Goldberg & Rao refers to the paper by Goldberg & Tarjan and highlight that Goldberg & Rao do not use the push/relabel algorithm but find blocking flows. But in my opinion, Tarjan only explains the push/relabel algorithm, I cannot find anything about blocking flows.

T. Cormen, "Introduction to algorithms", 3rd edition

The asymptotically fastest algorithm to date for the maximum-flow problem, by Goldberg and Rao, runs in time $O(min(V^{2/3}, E^{1/2}) E \lg{(V^2/E + 2)} * \lg{C})$, where $C = \max c(u,v)$. This algorithm does not use the push-relabel method but instead is based on finding blocking flows.

A. Goldberg & S. Rao, "Beyond the Flow Decomposition Barrier" (the original paper)

Using the blocking flow algorithm of Goldberg and Tarjan [1988], we get an $O (\Lambda m log(n^2/m)\log{U})$ bound.

Answer 1

They gave the wrong reference, for whatever reason, as have you have found out by yourself.

The blocking flow method you are supposed to use is the one given in

http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf, Section 8.3.