Searching for d-MPs with fast enumeration

Shin Guang Chen*, Yi-Kuei Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


Network theories have been developed for decades. They are now widely applied to solve many real-life problems. An active research field is the reliability evaluation of multistate networks. The most popular methods for such evaluation often use minimal paths (MP) or minimal cuts (MC) of the network. In these approaches, three basic steps exist: (a) searching for all MPs/MCs; (b) searching for all d-MPs/d-MCs from these MPs/MCs; (c) calculating union probability from these d-MPs/d-MCs. When the network is live, there are several minimum path vectors with respect to system state for d, namely d-MP, can be found. Steps a and c have great advances recently. This paper focuses on the searching for d-MPs by given MPs in terms of fast enumeration (FE), which was a recent advance in the integer programming problems in the literature. This paper is a first attempt to apply FE to the reliability evaluation of multistate networks. This paper also makes comparison with the well known algorithm for benchmarking. More complicated examples are also examined for illustrative purposes.

Original languageEnglish
Pages (from-to)139-147
Number of pages9
JournalJournal of Computational Science
StatePublished - 1 Nov 2016


  • d-MPs
  • Explicit enumeration
  • Fast enumeration
  • Minimal path
  • Network reliability

Fingerprint Dive into the research topics of 'Searching for d-MPs with fast enumeration'. Together they form a unique fingerprint.

Cite this