A Tutorial Exposition of Various Methods for Analyzing Capacitated Networks
Ali Muhammad Ali Rushdi *
Department of Electrical and Computer Engineering, Faculty of Engineering, King Abdulaziz University, P.O.Box 80204, Jeddah, 21589, Saudi Arabia.
Omar Mutab Alsalami
Department of Electrical and Computer Engineering, Faculty of Engineering, King Abdulaziz University, P.O.Box 80204, Jeddah, 21589, Saudi Arabia.
*Author to whom correspondence should be addressed.
Abstract
In order to assess the performance indexes of some practical systems having fixed channel capacities, such as telecommunication networks, power transmission systems or commodity pipeline systems, we propose various types of techniques for analyzing a capacitated network. These include Karnaugh maps, capacity-preserving network reduction rules associated with delta-star transformations, and a generalization of the max-flow min-cut theorem. All methods rely on recognizing the network capacity function as a random pseudo-Boolean function of link successes; a fact that allows the expected value of this function to be easily obtainable from its sum-of-products expression. This network capacity has certain advantages for representation of nonbinary discrete random functions, mostly employed in the analysis of flow networks. Five tutorial examples demonstrate the afore-mentioned methods and illustrate their computational advantages over the exhaustive state enumeration method.
Keywords: Capacitated networks, map method, reduction rule, max-flow min-cut theorem, star-delta transformation, pseudo-switching function.