Modify

Ticket #3468 (closed Bugs: fixed)

Opened 5 years ago

Last modified 17 months ago

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

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

Change History

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

dimacs max flow

comment:1 Changed 5 years ago by steven_watanabe

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

comment:2 Changed 3 years ago by jewillco

  • Milestone changed from Boost 1.41.0 to To Be Determined

comment:3 Changed 17 months ago by jewillco

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

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

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
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.