id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
580,Max Flow Algorithm,vfailla,Jeremiah Willcock,"{{{
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
}}}",Support Requests,closed,,graph,None,Not Applicable,invalid,,