Boost logo

Boost :

From: (noreply_at_[hidden])
Date: 2006-03-08 05:16:30

Support Requests item #1445526, was opened at 2006-03-08 11:16
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting:

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.
Category: None
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Vincenzo Failla (vfailla)
Assigned to: Nobody/Anonymous (nobody)
Summary: Max Flow Algorithm

Initial Comment:
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

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



You can respond by visiting:

This SF.Net email is sponsored by xPML, a groundbreaking scripting language
that extends applications into web and mobile media. Attend the live webcast
and join the prime developer group breaking into this new coding territory!
Boost-bugs mailing list

Boost list run by bdawes at, gregod at, cpdaniel at, john at