Home

Network Biology, 2021, 11(2): 97-124
[XML] [EndNote] [RefManager] [BibTex] [ Full PDF (940K)] [Comment/Review Article]

Article

Analyzing capacitated networks via Boolean-based coherent pseudo-Boolean functions

Ali Muhammad Ali Rushdi1, Omar Mutab Alsalami2
1Department of Electrical and Computer Engineering, Faculty of Engineering, King Abdulaziz University, P. O. Box 80200, Jeddah, 21589, Kingdom of Saudi Arabia
2Department of Electrical Engineering, College of Engineering, Taif University, P.O. Box 11099, Taif 21944, Kingdom of Saudi Arabia

Received 24 January 2021;Accepted 5 March 2021;Published 1 June 2021
IAEES

Abstract
This paper introduces a novel method for analyzing capacitated networks through the utilization of the concept of a "probability-ready expression" for a Boolean-based coherent pseudo-Boolean function. Our main concern is to assess the performance indexes of biology and ecology networks having fixed channel capacities. The technique introduced is based on constructing an exhaustive description (specifically, a value-entered Karnaugh map) for the pseudo-Boolean capacity function of the network via a generalization of the max-flow min-cut theorem. Then the function is expressed in a disjunctive-normal form (DNF) by obtaining the socalled 'contributions' of each entered value via standard Karnaugh maps. The technique heavily relies on the fact that the pertinent function is a coherent one, and it is self-checking since it must produce a DNF of solely uncomplemented Boolean literals. The notorious Inclusion-Exclusion (IE) Principle is ruled out as a practical means for converting the DNF of the capacity function into its probabilistic expectation (its expected value). Instead, a method is proposed for converting the DNF of the capacity function to a 'probability-ready expression' (PRE), which can be easily transformed, on a one-to-one basis into a probability function. Two tutorial examples demonstrate the afore-mentioned method and illustrate its computational advantages over the exhaustive state enumeration method and the IE method.

Keywords capacitated networks;map method;max-flow min-cut theorem;pseudo-Boolean function;probability-ready expression;exhaustive enumeration;inclusion-exclusion.


International Academy of Ecology and Environmental Sciences. E-mail: office@iaees.org
Copyright © 2009-2024 International Academy of Ecology and Environmental Sciences. All rights reserved.
Web administrator: office@iaees.org, website@iaees.org; Last modified: 2024/4/19


Translate page to: