COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 11 years ago

#11 closed defect (fixed)

Preflow and Tolerance

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: major Milestone:
Component: core Version: svn trunk
Keywords: Cc:
Revision id:

Description

The Tolerance can cause a bug in the Preflow algorithm. If there is no edge with epsilon or more capacity the source node can have surely positive excess. I think the algorithm should revised with the tolerance class and it would be nice to prove the correctness and the time complexity of the algorithm with tolerance.

The test generator could be found in my home dir.

This ticket is a copy of report #57 of the old bug tracking system. It refers to svn trunk -r3101. The original report was posted by Balazs Dezso.

Change History (1)

comment:1 in reply to:  description Changed 11 years ago by Balazs Dezso

Resolution: fixed
Status: newclosed

The problem is already solved in svn -r3380.

Replying to alpar:

The Tolerance can cause a bug in the Preflow algorithm. If there is no edge with epsilon or more capacity the source node can have surely positive excess. I think the algorithm should revised with the tolerance class and it would be nice to prove the correctness and the time complexity of the algorithm with tolerance.

The test generator could be found in my home dir.

This ticket is a copy of report #57 of the old bug tracking system. It refers to svn trunk -r3101. The original report was posted by Balazs Dezso.

Note: See TracTickets for help on using tickets.