Computational Comparison of Eight Methods for the Maximum Network Flow Problem

Publisher Website
Google Scholar
Abstract
There exist two approaches for solving the maximum network flow problem. In the fLrst approach, flow is augmented along paths and is always conserved at the vertmes In the second approach, flow is augmented through layers and is sometimes not conserved at some of the vertices. Many methods based on these two approaches are first briefly revmwed A computational comparison is then presented of eight of the methods--depth-first search, breadth-fLrst search, largestaugmentatmn, Dmic, layer-updating, Karzanov, Dimc-Karzanov, and Kinanwala-Rao. Problems with up to 1500 vertices and 7960 arcs have been tested. Computatmnal results show that Dnuc's method is better than all of the other methods. However, for small-sized problems (up to 25 vertices and 200 arcs), the performances of the depth-first and breadth-first methods are comparable to Dinic's method. Hence, with programming simphclty and memory space requirements taken into consideration, the former also seem to be a good chome for small problems.