Opened 13 years ago

Closed 10 years ago

#3468 closed Bugs (fixed)

kolmogorov_max_flow doesn't always find the maximum flow

Reported by: Jacob Stevenson <jstevenson131@…> Owned by: Andrew Sutton
Milestone: To Be Determined Component: graph
Version: Boost 1.40.0 Severity: Problem
Keywords: kolmogorov max flow Cc:

Description

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.

Attachments (1)

err.dat​ (3.0 KB ) - added by Jacob Stevenson <jstevenson131@…> 13 years ago.
dimacs max flow

Download all attachments as: .zip

Change History (4)

by Jacob Stevenson <jstevenson131@…>, 13 years ago

Attachment: err.dat​ added

dimacs max flow

comment:1 by Steven Watanabe, 13 years ago

Component: None → graph
Owner: set to Andrew Sutton

comment:2 by Jeremiah Willcock, 12 years ago

Milestone: Boost 1.41.0 → To Be Determined

comment:3 by Jeremiah Willcock, 10 years ago

Resolution: → fixed
Status: new → closed

(In [81536]) Applied patch from #7728 to fix B-K max-flow bug; fixes #7728; fixes #3468

Note: See TracTickets for help on using tickets.