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 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.     

A Method for Evaluating All the Minimal Cuts of a Graph

This paper presents a new technique to determine all minimal cuts for all the sink nodes in a non-planar network. The algorithm uses a subset method and an iterative process to achieve high efficiency. For an N-sink node network there are (2N - 1) possible combinations of nodes (non-empty subsets). These subsets are checked against several conditions to see if they can be transformed into minimal cutsets. An iterative process is used to generate these non-empty subsets efficiently so that the number of subsets to be checked is about (2N - 1)/2. Since this algorithm generates all the minimal cutsets for all nodes in one operation, it is faster compared to conventional methods which compute for one sink node at a time. Tests using random graphs showed a small cpu time per minimal cutset.     

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     

基于图的分布式平飞航迹关联算法

航迹关联是分布式传感器信息融合的关键问题之一,其主要问题在于多目标平飞航迹难以关联,而实际工程应用中无法实时获取方差数据又增加了关联难度。将同一传感器获取的平飞航迹抽象为图论中无分辨的点,应用综合B型关联理论计算各点间距,进而构造反映航迹间关联关系的双向连通图,并用邻接矩阵描述其关联拓扑关系。不同节点的公共观测连通图对应的邻接矩阵必然是相似的,继而将图二分为单点图及其对应补图,利用辩证的思想将补图所对应的邻接矩阵的特征值抽象为对应点的特征向量,最终将平飞航迹关联落脚至多维分配问题。实验仿真表明,该方法具有较好的关联效果。     

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.     

A recursive approach for enumerating minimal cutsets in a network

This paper presents a new recursive labelling algorithm for determining all minimal cutsets in a directed network, using an approach adapted from dynamic programming algorithms for the classical shortest route problem. The algorithm produces all minimal cutsets, and uses comparison logic to eliminate any redundant cutsets. Computational experience shows that: (1) the time per cutset varies linearly with the number of nodes but decreases exponentially with the density of the graph; and (2) whereas the algorithm's performance with regard to `change in the time per cutset vs. the number of nodes' is similar to other algorithms, it appears to exhibit superior performance where the time/cutset is compared to the density of the graph     

A Cutsets-Based Unified Framework to Evaluate Network Reliability Measures

This paper presents a minimal cutsets-based unified framework to evaluate some commonly used reliability measures: $g$-terminal, 2-terminal, and $k$-terminal reliability. In doing so, the paper proposes a single algorithm, which generates the network node sets. From these node sets, depending on the reliability measure(s), only those node sets are kept, which contains at least one node from the specified node set. These selected node sets form link-minimal cutsets. These minimal cutsets are used as an input to multi-variable inversion-based sum-of-disjoint product approach to obtain the unreliability expression thereafter. By solving several network examples of varied complexities, the comparison with the existing approach is provided.      

Bounding network-reliability using consecutive minimal cutsets

A subset of consecutive minimal cutsets of the set of cutsets is used to develop an efficient algorithm to compute an upper bound for the reliability of a network. The reliability is the probability that a path consisting only of functioning arcs exists between the source and the sink of the network. The nodes of this network are perfect, but the arcs are independent and either function or fail with known probabilities. For the case of source-to-sink planar networks, an approach to obtain a lower bound for the reliability of the network is also presented. Examples illustrate the use of the algorithm and show that the upper bound is, is many cases, better than that obtained by A.W. Shogan (1976)     

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.     

All-Terminal Network Reliability Using Recursive Truncation Algorithm

Exact calculation of all-terminal network reliability is a hard problem; its computational complexity grows exponentially with the number of nodes and links in the network. We propose the Recursive Truncation Algorithm (RTA), a bounding approximation algorithm, to estimate the all-terminal reliability of a given network with a pre-specified accuracy. RTA scans all minimal cutsets of the graph representing the network, and finds the weak cutsets of the graph by comparing failure probabilities of cutsets to an adaptive threshold which depends on the approximation accuracy. We calculate the unreliability of the network versus the probabilities of occurrence of failure in the weak cutsets, and the probabilities of co-occurrence of failure in several weak cutsets, simultaneously. In addition to the all-terminal reliability, the RTA computes an upper, and a lower bound for the estimated reliability. We demonstrate that the estimated all-terminal reliability of a given network is within a pre-specified accuracy, and is more precise than those obtained by existing methods.      

A New Algorithm for Symbolic System Reliability Analysis

This paper presents a new algorithm for symbolic system reliability analysis. The method is applicable to system graphs with unreliable branches or nodes. Each branch is directed or undirected. Element probabilities need not be equal, but their failures are assumed to be s-independent. The new method makes no attempt to generate mutually exclusive events from the set of paths or cutsets but uses a technique to reduce greatly the number of terms in the reliability expression. Actual programming results show that the new method can efficiently handle systems having fewer than 20 paths or cutsets between the input-output node pair.     

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.     

基于LonWorks技术的多通道数据采集与监控系统的设计与实现

介绍了采用神经元芯片对Ａ／Ｄ转换器和双端口ＲＡＭ进行控制的数据采集与监控系统的硬件实现与软件设计。通过消息在基于ＬｏｎＷｏｒｋｓ现场总线的节点间通信,将采集节点采集的数据通过网络双绞线传送到中央节点,存入双端口ＲＡＭ,上位机根据需要可读出数据,显示于监控界面。     

Computerized evaluation of water-supply reliability

The application of network reliability to maintenance and rehabilitation of water distribution systems is discussed. An algorithm converts a distribution system into a stochastic network in which arcs represent components with random life, and nodes represent demand points (junctions) between the components. Water supply reliability at a demand point is the reliability of the subnetwork defined by the source and the demand point. A simple reliability measure based on network connectivity is used to compute subnetwork reliability by the method of minimal pathsets or minimal cutsets. The point reliability values at the demand points can be used to draw a reliability surface; that surface offers a new approach to addressing water-supply infrastructure maintenance and rehabilitation issues. The methodology is illustrated by analyzing a case-study water system using a specially devised computer program. The proposed algorithm is not necessarily the most efficient, but is certainly the simplest. The reliability measure is based on water availability only, regardless of its quantity or quality     

1-Mbit virtually static RAM

The 1-Mb RAM utilizes a one-transistor, one-capacitor dynamic memory cell. Since all the refresh-related operations are done on chip, the RAM acts as a virtually static RAM (VSRAM). The refresh operations are merged into the normal operation, called a background refresh, the main feature of the VSRAM. Since the fast operation of the core part of the RAM is crucial to minimize the access-time overhead by the background refresh, 16 divided bit lines and parallel processing techniques are utilized. Novel hot-carrier resistant circuits are applied selectively to bootstrapped nodes for high hot-carrier reliability. N-channel memory cells are embedded in a p-well, which gives a low soft error rate of less than 10 FIT. 1-/spl mu/m NMOSFETs with moderately lightly doped drain structures offer fast 5-V operation with sufficient reliability. An advanced double-level poly-Si and double-level Al twin-well CMOS technology is developed for fast circuit speed and high packing density. The memory cell size is 3.5/spl times/8.4 /spl mu/m/SUP 2/, and the chip size is 5.99/spl times/13.8 mm./SUP 2/. Address access time is typically 62 ns, with 21-mA operating current and 30-/spl mu/A standby current at room temperature.     

On the modified nodal approach to network analysis

An algorithm to reduce the size of MNA matrices for switched and nonswitched networks is proposed through the use of cutsets. The procedure is simple and eliminates all diagonal zeros. Closed switches and EMF sources are handled identically. The final size of the matrix may be reduced to the number of nodes when no current-controlled elements are present.     

Circular Layout Cutsets: An Approach for Improving Consecutive Cutset Bounds for Network Reliability

In this paper, we introduce a new type of parameterized class of cutsets for the 2-terminal network reliability problem, called the circular layout (CL) cutsets with parameter k, and devise a polynomial time algorithm for computing upper bounds from such structures. The CL cutsets, and the devised bounding method are characterized by the following aspects. 1) CL cutsets include the well known class of consecutive minimal cutsets, introduced by Shanthikumar, as a proper subset. Thus, bounds obtained by our main algorithm yield strict improvements on the basic consecutive cutsets algorithm. We note that extensive empirical studies done to date have shown that the consecutive cutsets method, when empowered by heuristics for choosing suitable cutsets, yields competitive bounds. 2) CL cutsets satisfy the semilattice structure required by Shier's algorithm for computing upper bounds in time polynomial in the number of cuts in a given cutset. Thus, CL cutsets define a new class of efficiently constructible cutsets of polynomial size that benefit from such generalized algorithm. 3) For any fixed value of the parameter k, the devised bounding method can be adapted to satisfy stringent constant-time update constraints, required by the most probable state algorithm of Colbourn & Harms , for obtaining iteratively improvable bounds, without adding significant time overhead to the method. Moreover, the devised bounding algorithm is easy to implement, and the obtained numerical results show more than a 32% improvement over bounds obtained by the basic consecutive cutsets algorithm     

Minimum-distance bounds by graph analysis

The parity-check matrix of a linear code is used to define a bipartite code constraint (Tanner) graph in which bit nodes are connected to parity-check nodes. The connectivity properties of this graph are analyzed using both local connectivity and the eigenvalues of the associated adjacency matrix. A simple lower bound on the minimum distance of the code is expressed in terms of the two largest eigenvalues. For a more powerful bound, local properties of the subgraph corresponding to a minimum-weight word in the code are used to create an optimization problem whose solution is a lower bound on the code's minimum distance. Linear programming gives one bound. The technique is illustrated by applying it to sparse block codes with parameters [7,3,4] and [42,23,6]     

An Simple Enumeration of All Minimal Cutsets of an All-Terminal Graph

ＡｎＳｉｍｐｌｅＥｎｕｍｅｒａｔｉｏｎｏｆＡｌｌＭｉｎｉｍａｌＣｕｔｓｅｔｓｏｆａｎＡｌｌ－ＴｅｒｍｉｎａｌＧｒａｐｈＺｈａｎｇＨｏｎｇｆｅｎ（ＳｈｉｊｉａｚｈｕａｎｇＰｏｓｔａｌＣｏｌｌｅｇｅ，０５００２１，Ｐ．Ｒ．Ｃｈｉｎａ）ＡｎＳｉｍｐｌｅＥｎ...