Max Flow Algorithm

[vfailla]

Hi,
I'm a student in Computer Science and
Telecommunications. I'm working for my thesis job on
graph algorithms and I'm developping a code for the
k-cut and the multiterminal cut problem.

To calculate max flow/minimum s-t cut, I used the
Goldberg algorithm implemented in the Boost Library.

Now I like to have more information (f.e.: the
complexity) about Goldberg Algorithm used in Boost Library.

I already gave a look to references section of Boost
Project but I had some difficult to find the related
Goldberg article ("A New Max-Flow Algorithm", 1985).

However in a later article ("A New Approach to the
Maximum-Flow Problem", Goldberg and Tarjan 1986) a
complexity of O(n^3) for the Goldberg algorithm (1985)
is given.

After simulation tests, I think the algorithm
implemented in Boost Library has lower complexity than
O(n^3).

Is this possible? Is there someone has the Goldberg
article (1985)?
I will be grateful if someone can help me.

Thanks

[Jeremiah Willcock]

A different paper is cited at the top of the source file, and can be found at ​ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/94/1523/CS-TR-94-1523.pdf; the two C source files mentioned there can be found at ​http://www.avglab.com/andrew/soft.html