Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Submitted By: Vincenzo Failla (vfailla)
Assigned to: Nobody/Anonymous (nobody)
Summary: Max Flow Algorithm
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)
After simulation tests, I think the algorithm
implemented in Boost Library has lower complexity than
Is this possible? Is there someone has the Goldberg
I will be grateful if someone can help me.