8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! You helped me so much! :) (sorry for my late reply) $\endgroup$ – user1904159 Mar 18 '13 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.