#3929: Merge the max-flow min-cut code from Scott Clifford and Jerin Schneider
--------------------------+-------------------------------------------------
Reporter: jason | Owner: rlm
Type: enhancement | Status: closed
Priority: major | Milestone: sage-duplicate/invalid/wontfix
Component: graph theory | Resolution: duplicate
Keywords: |
--------------------------+-------------------------------------------------
Comment(by mvngu):
Replying to [comment:3 rlm]:
> Also, based on the presentation I saw from these two people, it is
questionable whether we want to find a more standard implementation of
this algorithm (as they are a dime a dozen, and maybe not all of them were
undergraduate projects...).
From my reading of the
[http://wiki.wstein.org/2008/480a/theprojects?action=AttachFile&do=get&target=max_flow_min_cut.py
source code], it looks like the code is using the Ford-Fulkerson
algorithm, which is pretty bad for some corner cases. And its complexity
is in general not polynomial. Of course, one obvious way to get polynomial
complexity is to use the modified algorithm by Edmonds and Karp. Chapter 6
from the following text is very relevant to this ticket.
* D. Jungnickel. Graphs, Networks and Algorithms. 3rd edition, Springer,
2008.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/3929#comment:6>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
