A different approach to the design and analysis of network algorithms
Date
2012-12-10
DOI
Authors
Kfoury, Assaf
Mizraei, Saber
Version
OA Version
Citation
Kfoury, Assaf; Mizraei, Saber. "A Different Approach to the Design and Analysis of Network Algorithms", Technical Report BUCS-TR-2012-019, Computer Science Department, Boston University, December 10, 2012. [Available from: http://hdl.handle.net/2144/11407]
Abstract
We review elements of a typing theory for flow networks, which we expounded in an earlier report (BUCS TR 2018). 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.