Code that I've written
Codes to find minimum cuts
The codes can be found here and input
files can be found here .
You can find a link to both a short (10 page) and long (130
page) paper about these codes here
These sources correspond to what is described in Matt
Levine's masters thesis. We reorganized and cleaned up quite a
bit. K is now much better, with more heuristics and dynamic
trees, using a dynamic tree implementation by Tamas Badics. We also
made sure that HO, NI, and K will return the cut itself, as well as
code for concurrent multicommodity flow
This is the code of Leong, Shor and Stein. It is described
is code for undirected graphs.
is code for directed graphs.
Hard instances for RELAXT-III:
files (in DIMACS format, tarred, compressed) are instances of a
minimum-cost flow problem on a particular 49 node graph. The
instances differ in the choice of capacities and demands. We ran
these problems using the RELAXT-III code of Bertsekas and Tseng. The
interesting thing that happened was the running times varied greatly.
A file with the name gte_bad.XXXX represents a graph which took XXXX
milliseconds ( on a circa 1990 computer). These seems to be bad
examples for the RELAXT-III code. Any good explanations?
These problems came about as subproblems in the
multicommodity flow code
of Leong, Shor, and Stein.