Techniques for Analyzing Capacitated Networks: A Tutorial Review

This chapter reviews various types of techniques utilized for analyzing capacitated networks, with an eye on assessing the performance indexes of practical systems having fixed channel capacities, such as telecommunication networks, power transmission systems or commodity pipeline systems. The techniques reviewed 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. The chapter is supplemented with an appendix, which introduces the concept of a “probability-ready expression” for a Boolean-based coherent pseudo-Boolean function.