Boost C++ Libraries: Ticket #580: Max Flow Algorithm https://svn.boost.org/trac10/ticket/580 <pre class="wiki">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 </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/580 Trac 1.4.3 Daryle Walker Fri, 03 Aug 2007 12:03:01 GMT component changed; severity set https://svn.boost.org/trac10/ticket/580#comment:1 https://svn.boost.org/trac10/ticket/580#comment:1 <ul> <li><strong>component</strong> <span class="trac-field-old">None</span> → <span class="trac-field-new">graph</span> </li> <li><strong>severity</strong> → <span class="trac-field-new">Problem</span> </li> </ul> Ticket Jeremiah Willcock Sat, 23 May 2009 16:25:10 GMT owner, status, severity changed https://svn.boost.org/trac10/ticket/580#comment:2 https://svn.boost.org/trac10/ticket/580#comment:2 <ul> <li><strong>owner</strong> changed from <span class="trac-author">jsiek</span> to <span class="trac-author">Jeremiah Willcock</span> </li> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">new</span> </li> <li><strong>severity</strong> <span class="trac-field-old">Problem</span> → <span class="trac-field-new">Not Applicable</span> </li> </ul> Ticket Jeremiah Willcock Sat, 23 May 2009 16:29:08 GMT status, resolution changed https://svn.boost.org/trac10/ticket/580#comment:3 https://svn.boost.org/trac10/ticket/580#comment:3 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> <span class="trac-field-old">None</span> → <span class="trac-field-new">invalid</span> </li> </ul> <p> A different paper is cited at the top of the source file, and can be found at <a class="ext-link" href="ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/94/1523/CS-TR-94-1523.pdf"><span class="icon">​</span>ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/94/1523/CS-TR-94-1523.pdf</a>; the two C source files mentioned there can be found at <a class="ext-link" href="http://www.avglab.com/andrew/soft.html"><span class="icon">​</span>http://www.avglab.com/andrew/soft.html</a> </p> Ticket