[boost] [Boost-bugs] [ boost-Support Requests-1445526 ] Max Flow Algorithm

From: SourceForge.net (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: 
https://sourceforge.net/tracker/?func=detail&atid=207586&aid=1445526&group_id=7586

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

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=207586&aid=1445526&group_id=7586

-------------------------------------------------------
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!
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642
_______________________________________________
Boost-bugs mailing list
Boost-bugs_at_[hidden]
https://lists.sourceforge.net/lists/listinfo/boost-bugs