Optimal consecutive‐2 systems of lines and cycles
Ding‐Zhu Du, F. K. Hwang · Networks · 1985
Abstract A consecutive‐2 system is a graph where each vertex can either work or fail and the system fails if and only if two vertices incident to the same edge both fail. The simplest probability structure attached to such systems is to assume that vertex i has probability p i of failing and the states of the vertices are stochastically independent. For a given graph G of n vertices and a given set P of n probabilities, an optimal consecutive‐2 system is the triple ( G,P,M ), where M is a mapping from P to the vertices of G such that the probability of the system failing is minimum. Consecutive‐2 systems have been widely studied when the graph is either a line or a cycle. In this paper we study optimal consecutive‐2 systems which consist of many lines or many cycles. Our results provide optimal mappings that depend only on the rankings of the individual failure probabilities and not on their actual values. Moreover, we show by examples that rankings alone are probably insufficient to solve cases more complex than those solved in this paper.