Network Analysis via Pseudo-Boolean Functions and Boole-Shannon Expansion
Omar Mutab Alsalami *
Department of Electrical Engineering, College of Engineering, Taif University, P.O. Box 11099, Taif 21944, Saudi Arabia.
Ali Muhammad Ali Rushdi
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
This paper shows the significant simplicities that can be realized for network analysis when the edge capacity is big enough to allow a large value of flow. We use a network decomposition method, which substantially simplifies network analysis. The pseudo-Boolean functions are repeatedly subjected to Boole-Shannon expansion about appropriate keystone variables until subexpressions with statistically independent terms are found. This method focuses on conditioning a complex network based on the possible states of a keystone element or the possible combinations of states of many keystone elements. Two demonstration examples with ample details are provided to demonstrate the applicability of the proposed method. Both examples indicate the effective utility of the Boole-Shannon expansion as a means for transforming a pseudo-Boolean function into a probability-ready expression and subsequently into a probability expression.
Keywords: Pseudo-Boolean function, probability-ready expression, capacitated networks, system reliability