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

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.