A Simple Universal Generating Function Method to Search for All Minimal Paths in Networks

作者：Yeh Wei Chang^*

来源：IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans , 2009, 39(6): 1247-1254.

DOI：10.1109/TSMCA.2009.2026209

• Binary-state
• minimal path (MP)
• network reliability
• universal generating function method (UGFM)

Evaluating network reliability is an important topic in planning, designing, and control of systems, and the minimal-path (MP) set is one of the fundamental tools for evaluating network reliability. A straightforward and simple algorithm is presented here for finding all MPs before calculating the binary-state network reliability between the source node and the sink node (i.e., one-to-one reliability). It is based on the universal generating function method (UGFM) and a generalized composition operator. The computational complexity of the proposed algorithm is also analyzed. Finally, an example is given to illustrate how all MPs are generated using the proposed UGFM.

• 出版日期2009-11
• 单位清华大学