Algorithms for Generating Minimal Cutsets by Inversion

This paper studies the problem of inverting minimal paths to obtain minimal cutsets (or vice versa) for s-coherent systems. The theoretical results lead to simplified inversion by a sequential method. Strategies are discussed for implementing these simplifications efficiently. Computational results, obtained by applying the algorithms to standard problems drawn from the literature, indicate that a substantial reduction in computational effort can be achieved by such simplifications.     

Minimal paths and cuts of networks exposed to common-cause failures

A method is suggested for determining the minimal cuts and paths of a general network with common-cause failures. The minimal paths (cuts) are deduced from simple network minimal paths (cuts) obtained for the network if the common-cause failures are ignored, by appropriate manipulations with sets of path (cut) branches and sets of branches interrupted by common-cause failures. Calculation procedures are presented for an effective application of the method, to evaluate the reliability indices of the network by taking into account the statistical dependence of the failure events. Two examples are included     

Modularizing, Minimizing, and Interpreting the K&H Fault-Tree

The verification by Worrell & Stack (W&S) of results previously obtained by Kumamoto & Henley (K&H) for a fault tree of an s-noncoherent system and its inverse and their correction of the three errors in the tree makes it possible to simplify the analysis by forming modules; this facilitates Boolean algebraic operations, so that both sets are described economically in their minimal forms, a subset of the prime implicants (p.i.'s). Quine's consensus operation is used to minimize and to find the p.i.'s. Corresponding to the MOCUS output for the inverse reported by K&H, which is neither minimal nor the set of p.i.'s, instead of 32 terms, there are 15 in the modularized set. Instead of the 42 p.i.'s obtained by both K&H and W&S, we have 17; 13 of these are a unique minimal form. Instead of 352 p.i.'s for the tree per both K&H and W&S, we have a 15-term minimal form, identical to the list of p.i.'s. The results are further analyzed as a contribution to the continuing discussion of the utility of minimal forms vis-a-vis the p.i.'s and of the consensus method.     

A Classification Tree Based Approach for the Development of Minimal Cut and Path Vectors of a Capacitated Network

This paper presents a holistic method that links together Monte-Carlo simulation, exact algorithms, and a data mining technique, to develop approximate bounds on the reliability of capacitated two-terminal networks. The method uses simulation to generate network configurations that are then evaluated with exact algorithms to investigate if they correspond to a network success or failure. Subsequently, the method implements commercially available software to generate a classification tree that can then be analyzed, and transformed into capacitated minimal cut or path vectors. These vectors correspond to the capacitated version of binary minimal cuts & paths of a network. This is the first time that these vectors are obtained from a decision tree, and in this respect, research efforts have been focused on two main directions: 1) deriving an efficient yet intuitive approach to simulate network configurations to obtain the most accurate information; and given that the classification tree method could for some applications provide imperfect or incomplete information without the explicit knowledge of the reliability engineer, 2) understand the relationship between the obtained vectors, and the real capacitated minimal cut & path vectors of the network, and its reliability. The proposed method has been tested on a set of case networks to assess its validity & accuracy. The results obtained show that the technique described is effective, simple, and widely applicable.     

The Maximum Error in System Reliability Calculations by Using a Subset of the Minimal States

The reliability of a system is evaluated from information about the minimal states, using Poincare's method (inclusion-exclusion). An equation is derived using the minimal paths, which gives the reliability (the probability of system success) as a function of the reliabilities of the components; the unreliability or probability of system failure is obtained by subtracting this from one. Dually, with the minimal cuts, an equation is derived which gives the system unreliability as a function of the unreliabilities of the components; the reliability is obtained by subtracting from one. If some of the minimal states are missing, unknown, or unused, an error is made in the calculation. The probability which is calculated from the minimal states is underestimated and its complement overestimated. In this paper a method is described for determining the maximum error, both absolute and relative, when: 1) the minimal states are all statistically independent (e.g., they have no states in common); and 2) every minimal state has the same probability p, where p is selected so as to maximize the error. It is shown that the error and its associated system probability depend only upon the ratio of the number of minimal states used to the total number of minimal states. A table of errors, system probabilities, and relative errors is given for values of this ratio 0.01 (0.01) 0.99.     

Inverting and Minimalizing Path Sets and Cut Sets

This paper describes a technique for generating the minimal cuts from the minimal paths, or vice versa, for s-coherent systems. The process is a recursive 2-stage expansion based upon de Morgan's theorems; ie, it is the inversion of a Boolean polynomial having all common-valued (either all 0 or all 1) components, so that the inverse also has only common-valued components of the opposite sign. There are procedural short cuts and Quine-type absorptions; absorptions put the polynomial into its minimalized form. The number of stages of recursion is equal to the number of terms (minimal states) in the starting polynomial. The minimal states of the inverse form are the terms of the inverse polynomial after minimalization. Since the system is s-coherent and all components are common-valued in either the original or Inverse minimal forms, the lists of minimal states are unique.     

A new simple algorithm for enumerating all minimal paths and cuts of a graph

There are many algorithms to enumerate MPS and MCS. All of these involve advanced mathematics. This paper presents a new simple algorithm to determine all minimal paths between specified single terminal pair of arbitrary graphs or to determine all minimal cuts when the graph is planar. The algorithm is based on elementary concept of graph theory and dual principle. This algorithm is fast and simple. An example illustrates the algorithm.     

On Complementation of Pathsets and Cutsets

This paper suggests a technique for generating the minimal cuts from the minimal paths, or vice-versa, for an s-coherent system. In this method, the path polynomial is expressed in a particular form and then complements of only simpler Boolean functions are required. Examples illustrate the method.     

基于最小覆盖集的高精度链路丢包率测量方法

为降低链路丢包率测量过程中网络资源消耗,提高测量的精度,该文提出一种基于最小覆盖集的高精度链路丢包率测量方法。通过最小覆盖集测量方法有效降低路由矩阵的秩,从而减少测量路径数量;采用线性方程组求解和Gibbs采样相结合的方法,有效提高测量的准确度。仿真实验结果表明,该文提出的算法需要较少的端到端测量路径,同时具备更高的精度。     

An efficient method for terminal and multiterminal pathset enumeration

The literature is abundant with algorithms for determining separately the paths for the single terminal pair, paths for multiterminal pairs and cuts for a specified terminal pair of any network, from knowledge of the reliability logic diagram (RLD). However, very few methods are available as efficient algorithms for enumerating simultaneously the paths between any single terminal pair, paths for multiterminal pairs and cuts for the specified terminal pair.The present paper provides a conceptually simple and computationally efficient algorithm to obtain simultaneously the paths between any single pair of terminals, paths for multiterminal pairs and the cuts for the specified terminal pair of interest of any complex network. The algorithm is easy and computationally economical and also applicable to graphs having both nodes and branches of finite non-zero failure probability.An illustrative example is provided to demonstrate the effectiveness of the proposed algorithm.     

A New Technique in Minimal Path and Cutset Evaluation

This paper presents a new technique for deducing the minimal paths and cutsets of a general network. A powerful concept of reducing the total number of minimal paths to its basic minimal paths is introduced. This concept reduces the computational time and required storage in deducing the minimal cutsets. A new technique for evaluating minimal cutsets has been adopted. Examples demonstrate the power of the technique in reducing the computational requirements as compared to the conventional method, and show that the task for analysing large systems now becomes trival.     

Reliability of two-stage weighted-k-out-of-n systems with components in common

This paper extends the existing one-stage weighted-k-out-of-n model to two-stage weighted-k-out-of-n models with components in common. Algorithms are developed to calculate the system reliability, and generate the minimal cuts & minimal paths of two-stage weighted-k-out-of-n systems. Reliability bounds for systems with s-dependent component failures are investigated based on the generated minimal cuts & minimal paths. Two types of two-stage weighted-k-out-of-n models, the SW-k-out-of-n model, and the PW-k-out-of-n model, can be applied to investigate reliability issues in network applications, such as the project management, and the shortest path problems. Examples are provided to demonstrate the developed models & algorithms.     

Minimal presentations for irreducible sofic shifts

We re-cast a theorem of Willems (1989) in terms of symbolic dynamics. We then present a new result which characterizes when an irreducible sofic shift (i.e., constrained system) has a unique minimal irreducible presentation     

Experimental results on preprocessing of path/cut terms in sim ofdisjoint products technique

Researchers have proposed cardinality-, lexicographic-, and Hamming-distance-order methods to preprocess the path terms in sum of disjoint products (SDP) techniques for network reliability analysis. For cutsets, an ordering based on the node partition associated with each cut is suggested. Experimental results showing the number of disjoint products and computer time involved in generating SDP terms are presented. Nineteen benchmark networks containing paths varying from 4 to 780, and cuts from 4 to 7376, are considered. Several SDP techniques are generalized into three propositions to find their inherent merits and drawbacks. An efficient SDP technique is then used to run input files of paths/cuts preprocesses using cardinality-, lexicographic-, and Hamming-distance-ordering, and their combinations. The results are analyzed, showing that preprocessing based on cardinality or its combinations with lexicographic-, and/or Hamming-distance-ordering performs better     

E.I.R.P. allocation in single-destination f.d.m.a. satellite communication systems

The optimum allocation of downlink e.i.r.p. in a satellite communication system utilising single-destination f.d.m.a. carriers and a downlink multiple-beam antenna (m.b.a.) is considered. The optimum gain setting for the m.b.a. is determined and it is shown that this setting is independent of the level of the intermodulation and front-end noise generated by the satellite. The optimum allocation is expressed in terms of simple formulae which can be used for adaptive as well as static allocation of satellite power and antenna gain.     

Minimal pathset and minimal cutsets using search technique

Application of graph theory to reliability analysis was first made in 1970 ^[1]. Over the years, a large number of computer programmes have been developed to determine the spanning trees, the minimal paths and cutsets, which are essential for determining the reliability of the network. In recent years, there has been an interest 2., 4. in developing small desk top calculators for specific purposes, which could be used by the designers of transportation systems, communication systems, etc. In this article the authors present an approach to design a microprocessor based equipment to determine minimal pathset and minimal cutset from the incidence matrix of the graph. The authors have presented a new design approach, based on search technique. The salient feature of the new approach is a novel tracing process in which the desired graph is traced by operating a set of constraints. The new design approach has already been used by the authors to develop a microprocessor based spanning tree generator 2., 3..     

A new method for system reliability bounds

It has been established that symbolic reliability evaluation problem is an N.P. complete problem and as such is computationally infeasible for large networks. This has led to increased efforts in search for more fast exact techniques as well as better approximate methods.This paper proposes an algorithm for determining improved (tighter) upper and lower bounds on system reliability of general (i.e. non-series-parallel) systems. The proposed algorithm, like most existing methods, requires the knowledge of all simple paths and minimal cutsets of the system. The system success (failure) function is the union of all simple paths (minimal cutsets). The system success and failure functions are then modified to multinominal form and these expressions are interpreted as proper probability expressions using some approximations. The proposed algorithm gives better bounds as compared to the min-max method, the method of successive bounds, Esary-Proschan bounds and Shogan bounds and is illustrated by an example.     

A Computer Program for Approximating System Reliability

A computer program, which provides bounds for system reliability, is described. The algorithms are based on the concepts of success paths and cut sets. A listing of the elements in the system, their predecessors, and the probability of successful operation of each element are the inputs. The outputs are the success paths, the cut sets, and a series of upper and lower reliability bounds; these bounds converge to the reliability which would be calculated if all the terms in the model were evaluated. The algorithm for determining the cuts from the success paths is based on Boolean logic and is relatively simple to understand. Two examples are described, one of which is very simple and the computation can be done by hand, and a second for which there are 55 success paths and 10 cuts and thus machine computation is desirable.     

Cutset Analysis of Networks Using Basic Minimal Paths and Network Decomposition

The concept of basic minimal paths has been introduced, and its use in deducing the node cutsets of a network was described. This 3 paper deals with two important aspects of basic minimal paths: 1) the deduction of link cutsets from node cutsets, and 2) reduction of computational requirements in deducing the basic minimal paths using network decomposition.     

Minimal Cuts up to Third Order in a Planar Graph

This paper presents a new algorithm to determine all minimal cuts up to third order that isolate some sink node from all source nodes in a planar graph. The algorithm has the advantage of having a linear complexity, which makes the problem tractable as opposed to path oriented methods, where path determination grows exponentially with the size of the graph. This algorithm can be used when the size of the graph requires computer assistance, and it can simplify the application to large systems, of reliability evaluation techniques based on minimal cuts. The limitation of cuts up to third order has a numerical reason since cuts of higher order often negligibly affect the system indexes. A computer application to a graph that models an urban power distribution network shows the algorithm's capacity to handle complex problems and reduce CPU time.