A permutation-and-backtrack approach for reliability evaluation in multistate information networks

Shin Guang Chen, Yi Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Nowadays, people live heavily on information systems to handle their business and schedules. A reliable information system helps people smoothly and efficiently deal with their daily-life affairs. An information system usually consists of connected software and hardware components, and can be modeled by connected graphs. In network theory, such graphs are called multistate information networks. Therefore, the reliability of an information system can be evaluated by network theory, namely network reliability. The most popular approach to evaluate network reliability is the three-stage-approach (TSA), which involves (a) finding all minimal paths (MPs), (b) finding all d-system vectors (d-SVs), and (c) calculating the union probability of d-SVs for reliability. Approaches for creating all MPs has been reported. There is a need for a more efficient approach to generate all d-SVs for such calculation. In this article, an approach based on permutation-and-backtrack facility is proposed to generate all such d-SVs. The efficiency of this approach is generally accepted to be superior to the existing approaches. The proposed approach provides us an efficient, and simple way to speed up TSA as a more powerful tool for evaluating the reliability of multistate information networks.

Original languageEnglish
Article number125024
JournalApplied Mathematics and Computation
StatePublished - 15 May 2020


  • d-system vector
  • Minimal path
  • Multistate information network
  • Network reliability
  • Permutation-and-backtrack

Fingerprint Dive into the research topics of 'A permutation-and-backtrack approach for reliability evaluation in multistate information networks'. Together they form a unique fingerprint.

Cite this