https://svn.boost.org/trac10/ticket/3468 <p> On some graphs kolmogorov_max_flow finds a max flow value slightly less than push_relabel_max_flow. I've found the problem becomes more common for larger graphs. Using the official example scripts (from v 1.40.0) on the attached dimacs file push_relabel finds flow = 102 while kolmogorov finds flow = 100. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/3468 Trac 1.4.3 Jacob Stevenson <jstevenson131@…> Sun, 20 Sep 2009 20:54:07 GMT https://svn.boost.org/trac10/ticket/3468 https://svn.boost.org/trac10/ticket/3468 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">err.dat</span> </li> </ul> <p> dimacs max flow </p> Ticket Steven Watanabe Mon, 21 Sep 2009 03:38:45 GMT https://svn.boost.org/trac10/ticket/3468#comment:1 https://svn.boost.org/trac10/ticket/3468#comment:1 <ul> <li><strong>owner</strong> set to <span class="trac-author">Andrew Sutton</span> </li> <li><strong>component</strong> <span class="trac-field-old">None</span> → <span class="trac-field-new">graph</span> </li> </ul> Ticket Jeremiah Willcock Wed, 08 Dec 2010 19:43:57 GMT https://svn.boost.org/trac10/ticket/3468#comment:2 https://svn.boost.org/trac10/ticket/3468#comment:2 <ul> <li><strong>milestone</strong> <span class="trac-field-old">Boost 1.41.0</span> → <span class="trac-field-new">To Be Determined</span> </li> </ul> Ticket Jeremiah Willcock Sun, 25 Nov 2012 20:13:27 GMT https://svn.boost.org/trac10/ticket/3468#comment:3 https://svn.boost.org/trac10/ticket/3468#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-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/81536" title="Applied patch from #7728 to fix B-K max-flow bug; fixes #7728; fixes #3468">[81536]</a>) Applied patch from <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/7728" title="#7728: Bugs: boykov_kolmogorov_max_flow does not always compute a max flow (closed: fixed)">#7728</a> to fix B-K max-flow bug; fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/7728" title="#7728: Bugs: boykov_kolmogorov_max_flow does not always compute a max flow (closed: fixed)">#7728</a>; fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/3468" title="#3468: Bugs: kolmogorov_max_flow doesn't always find the maximum flow (closed: fixed)">#3468</a> </p> Ticket