COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Opened 16 years ago

Closed 16 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 16 years ago by Balazs Dezso

Resolution: → fixed
Status: new → closed

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.