Here are some results as a guideline. Problem | MaxFlow ---------------+-------------- simple1000 | 1000 simple10000 | 10000 simple100000 | 100000 simple1000000 | 1000000 ---------------+-------------- braid1000 | 400 braid10000 | 2368 braid100000 | 6805 braid1000000 | 60329 ---------------+-------------- complex1000 | 251153 complex10000 | 25449115 complex100000 | 2571625765 complex1000000 | 256574619774 Caveats/Hints: - for larger problems use "long maxFlow", i.e. 64bit ints. - if you use recursive depth first search, you will run out of stack for braid100000 (and braid1000000); you can increase the stack size using command line flags: java -server -Xss100m MaxFlow braid1000000 - be careful with your depth first search implementation: braidXXX has exponentially many pathes, but this not a problem, because we want "augmenting pathes" and there are a lot less, luckily. So make sure that depth first search only adds edges that have a positive, non-zero residual capacity, and make sure you do not go on again from nodes you have already inspected (e.g. the pseudo- code for DFS used a VISITED label for every node seen). Here is some sample timing information: Problem | MaxFlow ---------------+------------ simple1000 | 0.3 secs simple10000 | 16 secs simple100000 | 45 mins simple1000000 | 4356 mins ---------------+------------ braid1000 | 0.4 secs braid10000 | 3.4 secs braid100000 | 2 mins braid1000000 | 187 mins ---------------+------------ complex1000 | 0.7 secs complex10000 | 58 secs complex100000 | 123 mins complex1000000 | 11300 mins And here are runtimes for a version that uses breadth-first search for finding augmenting pathes: Problem | MaxFlow ---------------+------------ simple1000 | 0.2 secs simple10000 | 0.8 secs simple100000 | 2.9 secs simple1000000 | 38 secs ---------------+------------ braid1000 | 0.2 secs braid10000 | 5 secs braid100000 | 4 mins braid1000000 | 360 mins ---------------+------------ complex1000 | 0.3 secs complex10000 | 1.2 secs complex100000 | 1.5 mins complex1000000 | 151 mins