Modify

Opened 8 years ago

Closed 5 years ago

#3468 closed Bugs (fixed)

kolmogorov_max_flow doesn't always find the maximum flow

Reported by: Jacob Stevenson <jstevenson131@…> Owned by: asutton
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@…> 8 years ago.
dimacs max flow

Download all attachments as: .zip

Change History (4)

Changed 8 years ago by Jacob Stevenson <jstevenson131@…>

dimacs max flow

comment:1 Changed 8 years ago by steven_watanabe

  • Component changed from None to graph
  • Owner set to asutton

comment:2 Changed 7 years ago by jewillco

  • Milestone changed from Boost 1.41.0 to To Be Determined

comment:3 Changed 5 years ago by jewillco

  • Resolution set to fixed
  • Status changed from new to closed

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

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain asutton.
The resolution will be deleted. Next status will be 'reopened'.
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.