A different approach to the design and analysis of network algorithms
Assaf J. Kfoury, Saber Mizraei · 2012
We review elements of a typing theory for flow networks, which we expounded in an earlier report [19]. To illustrate the way in which this typing theory offers an alternative framework for the design and analysis of network algorithms, we here adapt it to the particular problem of computing a maximum-value feasible flow. The result of our examination is a max-flow algorithm which, for particular underlying topologies of flow networks, outperforms other max-flow algorithms. We point out, and leave for future study, several aspects that will improve the performance of our max-flow algorithm and extend its applicability to a wider class of underlying topologies.