A Merge Search Approach to Find Minimal Path Vectors in Multistate Networks

Yi-Kuei Lin, Shin Guang Chen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


A new approach namely merge search (MS) is proposed to search for minimal path vectors (MPV) in multistate networks (MSN). Also, a new advance in solving integer programming problems namely fast enumeration (FE) is integrated in this approach. Such an integrated approach can greatly improve the time efficiency of searching for MPV in MSN. Traditionally, searching for MPV in MSN involves three steps: (a) enumerate all feasible flow vectors; (b) transform these vectors to corresponding state vectors; (c) filter out MPV from these state vectors. Steps (a) and (c) are bottlenecks. Explicit enumeration is usually engaged in solving Step (a), and pairwise comparison is usually employed in solving Step (c). The integrated approach uses FE to solve Step (a), and MS to solve Step (c) instead. Some numerical examples are explored to show the superior time efficiency of the proposed approach. The results show that the proposed new approach is valuable in solving the search of MPV in MSN.

Original languageEnglish
Article number1750005
JournalInternational Journal of Reliability, Quality and Safety Engineering
Issue number1
StatePublished - 1 Feb 2017


  • Minimal path vector (MPV)
  • fast enumeration (FE)
  • merge search
  • minimal path
  • multistate network

Fingerprint Dive into the research topics of 'A Merge Search Approach to Find Minimal Path Vectors in Multistate Networks'. Together they form a unique fingerprint.

Cite this