Enumeration of minimal cutsets of an undirected graph

Cutsets and tiesets are needed to calculate reliability of or maximal flow through a network. Algorithms for enumeration of these cutsets and tiesets are being designed to facilitate these calculations. However, these algorithms either involve advanced mathematics or are based on technical notions and ideas such as fault tree analysis, etc. We have given here two different algorithms for enumerating minimal cutsets of an undirected graph (i.e. with feedback). An algorithm, proposed to enumerate minimal cutsets of an acyclic directed graph with adjacent nodes, is also shown to hold for an undirected one with some modifications; the second one is for finding minimal cutsets of a general undirected graph, which holds good for a directed one as well. Our algorithms are simple and do not need any prior knowledge of reliability notions or ideas, or advanced mathematics. Three examples are given to illustrate the algorithms.     

Simple enumeration of minimal cutsets of acyclic directed graph

Two methods are given that use combinations of nodes to enumerate all minimal cutsets. One simply has to enumerate all combinations of orders 1 to N-3 of nodes from 2 to N-1, where N is the total number of nodes. Collecting only those symbols of links of first row of adjacency matrix and in the rows given in a combination that are not in the columns of the combination, a cutset of an acyclic directed graph having all adjacent nodes is obtained. To obtain the cutsets of a general acyclic directed graph, four rules are given for deletion of those combinations that yield redundant and nonminimal subsets. The rules provide a reduced set of combinations, which then gives rise to minimal cutsets of a general graph. Three examples illustrate the algorithms     

Enumeration of minimal paths of modified networks

A method is presented for enumeration of minimal paths of networks generated by sequential modifications of an initial network, based upon step wise reformation of minimal paths sets associated with network modifications. The method can be applied for an effective enumeration of minimal paths of various extensions and reinforcements of an existing network in the network reliability analysis for the expansion planning. An illustrative example is included.     

Enumeration of minimal cuts of modified networks

A method is presented for enumeration of minimal cuts of networks obtained by modification of an initial network, based upon reformation of minimal cut sets of this network. The proposed method provides an efficient tool for reliability analysis of various modifications of an existing network for network expansion or reinforcement evaluation and planning. An illustrative example is included.     

Mathematical foundations of minimal cutsets

Since their introduction in the reliability field, binary decision diagrams have proved to be the most efficient tool to assess Boolean models such as fault trees. Their success increases the need of sound mathematical foundations for the notions that are involved in reliability and dependability studies. This paper clarifies the mathematical status of the notion of minimal cutsets which have a central role in fault-tree assessment. Algorithmic issues are discussed. Minimal cutsets are distinct from prime implicants and they have a great interest from both a computation complexity and practical viewpoint. Implementation of BDD algorithms is explained. All of these algorithms are implemented in the Aralia software, which is widely used. These algorithms and their mathematical foundations were designed to assess efficiently a very large noncoherent fault tree that models the emergency shutdown system of a nuclear reactor     

Enumeration of all cutsets of a graph

A computer program has been written which can be used for listing all the cutsets of a graph. The program can be applied to connected graphs having a maximum of 10 vertices and 20 edges.     

Enumeration of node cutsets for an s-t network

In this paper an algorithm has been presented for the enumeration of minimal cutsets due to the failure of nodes only. The algorithm adopted reduction of the incidence matrix due to the failure of the set of nodes that causes the loss of connectivity between the source and terminal node. An example has been included to demonstrate the algorithm.     

Enumeration of all circuits or cutsets of a graph

A computer program for the enumeration either of all the circuits or of all the cutsets of a nonoriented graph is described. It can be easily adapted for use with oriented graphs and for the enumeration of Hamilton circuits.     

A block matrix representation of permutation networks

This work provides a mathematical framework for topologically-independent analysis of permutation networks. First, a structure-dependent representation is provided using matrices whose entries are switching expressions. Then, a transformation is presented which maps these matrices into structure-independent representations which are matrices whose entries are 0/1 matrices. Algebraic tools for manipulating the second type of matrices are also provided. Notions such as permutations realizable by a network, the rearrangeability property, and series and parallel connections of networks are defined and discussed with regard to the proposed representations.     

Comments on `Enumeration of all minimal cutsets for a node pair ina graph'

The commenters point out that the algorithm of S.A. Kumar and S.H. Lee for the enumeration of all minimal s-t cutsets is defective (see ibid., vol.R-26, p.51-5, April 1979). It is illustrated through an example that their algorithm misses several minimal cutsets. The commenters cite two reasons for this: the adjacency problem and the back-vertex problem     

Novel matrix representation for OFDM/OQAM systems

In orthogonal frequency division multiplexing/offset quadrature amplitude modulation (OFDM/OQAM) systems, the relationship between the input of the synthesis filter bank (SFB) and the output of the analysis filter bank (AFB) is much more complicated than OFDM due to its special prototype filter. By analyzing the trans-multiplexer response characteristics, an equivalent trans-multiplexer matrix is proposed to describe the relationship between the input and the output. With the equivalent matrix, the output can be easily computed using matrix multiplication with the input. Moreover, with the inverse of the equivalent trans-multiplexer matrix, imaginary interference can be eliminated using the precoding method. The simulation results show the correctness of the equivalent trans-multiplexer matrix.     

Geometric properties of nonlinear networks containing capacitor-only cutsets and/or inductor-only loops. Part II: Symmetries

This paper is the last in a two-part sequence which studies nonlinear networks, containing capacitor-only cutsets and/or inductor-only loops, from the geometric coordinate-free point of view of the theory of differentiable manifolds. For such circuits, it is shown that (subject to certain assumptions) there is a naturally defined Lie group action of on the state space ofN, where ₀ is the sum of the number of independent capacitor-only cutsets and the number of independent inductor-only loops. Circuit theoretic sufficient conditions on the reactive constitutive relations are derived for the circuit dynamics to be invariant under this Lie group action.This work was supported by the Natural Sciences and Engineering Research Council of Canada, under Grant Number A7113, and by scholarships from the Natural Sciences and Engineering Research Council of Canada and the Ontario Provincial Government.     

Geometric properties of nonlinear networks containing capacitor-only cutsets and/or inductor-only loops. Part I: Conservation laws

This paper is the first in a two part sequence which studies nonlinear networks, containing capacitor-only cutsets and/or inductor-only loops from the geometric coordinate-free point of view of differentiable manifolds. Given such a nonlinear networkN, with °₀ equal to the sum of the number of independent capacitor-only cutsets and the number of independent inductor-only loops, we establish the following: (i) circuit theoretic sufficient conditions to guarantee that the set ⁰, of equilibrium points is a ₀-dimensional submanifold of the state space ofN; (ii) circuit theoretic sufficient conditions for the condition thatN has ₀ independent conservation laws and hence that through each point of the state space ofN, there passes a codimension ₀ invariant submanifold ^* of the network dynamics; (iii) circuit theoretic sufficient conditions to guarantee that the manifolds ^* and ⁰ intersect transversely.This work was supported by the Natural Sciences and Engineering Research Council of Canada, under Grant Number A7113, and by scholarships from the Natural Sciences and Engineering Research Council of Canada and the Ontario Provincial Government.     

Signal-flowgraph representation of electronic-amplifier networks

It is shown that the basic action of the differential-input earthed-output type of operational amplifier may be given a flowgraph representation with a type of graph that is more general than those of Coates and Mason. Examples of embedded amplifiers are given to show the use of these graphs for the analysis of particular amplifier circuits.     

The design of survivable directed networks

We study a survivable network design problem:the directed network design problem with connectivity constraints (DNCC). Some applications in telecommunications are presented. We discuss two integer linear programming models for DNCC, and relate these. The main body of the paper is a study of DNCC from a polyhedral point of view. We give several classes of nonredundant inequalities for polytopes associated with the problem. A cutting plane algorithm based on the polyhedral results is described and some computational results are given.     

Outer-product matrix representation of optical orthogonal codes

In this letter, we introduce a whole new approach in defining and representing optical orthogonal codes (OOCs), namely, outer-product matrix representation. Instead of applying commonly used approaches based on inner product to construct OOC codes, we use the newly defined approach to obtain a more efficient algorithm in constructing and generating OOC codes. The outer-product matrix approach can obtain a family of OOC codes with a cardinality closer to the Johnson upper bound, when compared with the previously defined accelerated greedy algorithm using the inner-product approach. We believe the new look introduced in this letter on OOCs could help to devise new approaches in designing and generating OOC codes, using the rich literature in matrix algebra.     

关于有向环网平均直径的研究

根据有向双环网络平均直径与其最小路径图(L-型瓦)4个几何参数(a、b、p和q)之间的关系,提供了平均直径的计算公式,并提供了快速计算平均直径的算法。提供了构造有向三环网络的最小路径图(等价树)的新方法,研究了三环网络的任意2点之间的最短路径与等价树的层之间的关系,给出了三环网络平均直径的计算公式和算法。实验结果表明:同一网络的平均直径约为直径的一半;在一个无限族中,直径达到最小值时平均直径不一定为最小值,但平均直径为最小值时直径一定为最小值。研究表明平均直径比直径更能准确地反映环网的传输效率,所以平均直径应成为设计最优网络重要的依据之一。