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

<p>The blocking flow method you are supposed to use is the one given in</p>

<p><a href="http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf">http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf</a>,
Section 8.3.</p>

CC BY-SA 3.0
2013-03-18T12:24:50.883Z
Thank you! You helped me so much! :)

(sorry for my late reply)
user1904159
CC BY-SA 3.0
2013-03-06T15:32:01.350Z
2013-03-06T15:32:01.350Z
Olaf
<p>I want to implement the Goldberg &amp; Rao algorithm for finding a maxflow in a graph. My problem is the update step where every paper and report is stating &quot;In the resulting graph, find a blocking flow or a flow of value Delta.&quot; They all refer to Goldberg &amp; Tarjan for finding a blocking flow. There are two things I don't understand:</p>
<ol>
<li>How am I supposed to find a flow of value Delta?</li>
<li>But more important: how can I find a blocking flow?</li>
</ol>
<p>Regarding questions 2: I read the two papers (the one by Goldberg &amp; Tarjan &quot;A New Approach to the Maximum-Flow Problem&quot; and the one about dynamic trees - both were not that hard to understand). Every paper/report/book about Goldberg &amp; Rao refers to the paper by Goldberg &amp; Tarjan and highlight that Goldberg &amp; 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.</p>
<blockquote>
<h3>T. Cormen, &quot;Introduction to algorithms&quot;, 3rd edition</h3>
<p>The asymptotically fastest algorithm to date for the maximum-flow problem, by Goldberg and Rao, runs in time <span class="math-container">$O(min(V^{2/3}, E^{1/2}) E \lg{(V^2/E + 2)} * \lg{C})$</span>, where <span class="math-container">$C = \max c(u,v)$</span>. This algorithm does not use the push-relabel method but instead is based on finding blocking flows.</p>
<h3>A. Goldberg &amp; S. Rao, &quot;Beyond the Flow Decomposition Barrier&quot; (the original paper)</h3>
<p>Using the blocking flow algorithm of Goldberg and Tarjan [1988], we get an <span class="math-container">$O (\Lambda m log(n^2/m)\log{U})$</span> bound.</p>
</blockquote>

<ds.algorithms><graph-theory><graph-algorithms><max-flow>
Goldberg&Tarjan: How to find a blocking flow in a graph
user1904159
# Goldberg&Tarjan: How to find a blocking flow in a graph

(Asked by: username_0 on 2013-02-28)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, max-flow

---

## 1 answers

### Answer by username_1 on 2013-03-06. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you! You helped me so much! :)  (sorry for my late reply)  

---

