An efficient algorithm for the reliability of consecutive-k-n networks

Jen Chun Chang*, Rong-Jaye Chen, Frank K. Hwang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


A consecutive-k-n network is a generalization of the well-known consecutive-k-out-of-n system, and has many practical applications. This network consists of n + 2 nodes (node 0, the source, nodes 1, 2 ..., n, and node n + 1, the target) and directed links from node i to node j (0 ≤ i < j ≤ n + 1, j - i ≤ k). Because all nodes except the source and target, and all links are fallible, the network works if and only if there exists a working path from the source to the target. For the k = 2 case, based on identical node reliabilities and some assumptions on link reliabilities, Chen, Hwang and Li (1993) gave a recursive algorithm for the reliability of the consecutive-2-n network. In this paper we give a closed form equation for the reliability of the general consecutive-k-n network by means of a novel Markov chain method. Based on the equation, we propose an algorithm which is more efficient than other published ones for the reliability of the consecutive-k-n network.

Original languageEnglish
Pages (from-to)159-166
Number of pages8
JournalJournal of Information Science and Engineering
Issue number1
StatePublished - 1 Jan 2003


  • Algorithm
  • Complexity
  • Consecutive-k-n network
  • Consecutive-k-out-of-n system
  • Reliability

Fingerprint Dive into the research topics of 'An efficient algorithm for the reliability of consecutive-k-n networks'. Together they form a unique fingerprint.

Cite this