计算无圈有向网络ST可靠性的一个新方法

本文考虑计算无圈有向网络的ＳＴ可靠性问题（至少存在一条从源点ｓ到汇点ｔ的正常运行道路的概率）。文章引进了深度优先搜索（Ｄｅｐｔｈ－ＦｉｒｓｔＳｅａｒｃｈ）有序根树的概念并提出一个新的计算无圈有向网络ＳＴ可靠性的拓扑公式。以该公式为基础,我们利用ＤＦＳ方法提出一个新的计算无圈有向网络ＳＴ可靠性算法,它能生成简洁的可靠性表达式,进而有效地计算无圈有向网络的ＳＴ可靠性。两个例子例证了我们的结论     

计算大型有向网络可靠度的一种新方法

本文提出了计算大型有向网络可靠度的一种新方法,它是以网络流理论为基础的分解算法。把大型网络按照本文给出的规则划分为若干子网络,再利用本文提出的收缩顶点概念和分解算法,可求出大型有向网络可靠度。     

网络系统可靠度的BDD算法

文中研究3-状态设备网络系统2-终端可靠度的计算问题。BDD是布尔函数的图形表示形式。武小悦和沙基昌提出了一个采用BDD方法求2-状态网络系统的不交化最小路集,从而直接计算网络系统可靠度的算法。通过引入简化技术,结合归约公式和BDD技术,给出了一个计算3-状态设备网络2-终端可靠度的一个新算法;算法有效地消除了冗余项,并且产生的分枝树具有结点少,可有效得到可靠度符号表达式。     

通信网络的可靠性评估

通信网络的可靠性评估是一个难题。目前人们只对环型网和树型网进行可靠性分析。本文首先定义了通信网络的可靠性，依据图论提出了网络生成树的计算方法，以及网络可靠度的估算公式。最后给出了一个栅格型网的可靠度估算示例。     

K终端可靠度分解算法中多边形→链简化定理的完善

无向网络K终端可靠度的分解算法中,包括多边形→链简化在内的等可靠度简化和分解定理结合,可以降低算法的复杂度。本文完善了边随机无向网络和混合随机无向网络的4#,6#,7#型多边形→链简化定理。计算机编程验证了其正确性。     

一种计算网络加权可靠度的新算法

提出了一种计算网络加权可靠度的新算法,提出了空量饱和状态的概念,给出了最小路展开为限定子集之和和递推公式,基于该递推公式最小的展开将不再生成与网络加权可靠度无关的限定子集,省去了不必要的展开计算,因此本算法较以往算法具有较小的计算量。     

利用因子分解方法计算网络的根通信可靠性

本文使用因子分解(factoring)的方法计算网络的根通信可靠性(存在从根点到每一个其它结点正常运行道路的概率)。我们充分利用无圈有向网络的拓扑结构提出了两个新的可靠性保护缩减(Reliability-Preserving Reduction)和一个进行因子分解的选边规则。在此基础上,给出一个因子分解算法(factoring algorithm)。对于不是非常稠密的网络,该算法是非常有效的。     

基于容斥原理与不交和公式的一个计算网络可靠性方法

这篇文章考虑了网络从源点ｓ到某些特定终点Ｋ的ＳＫＴ可靠性问题，文章基于容斥原理和不交和公式提出的一个新的拓扑公式，它比相应的Ｓａｔｙａｎａｒａｙａｎｎａ公式含有更少的项和算术运算，在此公式基础上，提出一个计算网络ＳＫＴ可靠性算法，它改进了相应的Ｓａｔｙａｎａｒａｙｍａｎｎａ算法，能产生更紧的可靠性表达式。     

求网络总可靠度的状态空间树法和精确分解算法

本文提出了求通信网络总可靠度的状态空间树法。它直接产生网络图的一个不交化树多层多项式,优点是计算量较小[计算时间复杂度为0(?),(?)为边数,n_1为叶数],所得表达式较短。在此基础上应用超图理论提出了求通信网络总可靠度的精确分解算法。用它进行网络图的m次分解,一台计算机所能计算的通信网络规模可以扩大m倍。     

无向通信网端对端可靠性通用算法

针对无向通信网的节点和链路都存在失效的问题,提出了端到端可靠性的通用算法。对无向网络基于概率论的分解定理进行证明,介绍了无向网络的简化与分解算法及流程,并分析了端到端可靠度的计算准则,针对3种复杂程度无向网络进行了分析比较,最后提出一种无向通信网端对端可靠性通用算法。分析结果表明提出的通用算法适合节点和链路都不可靠的情...     

A New Algorithm for the Reliability Analysis of Multi-Terminal Networks

In a probabilistic network, source-to-multiple-terminal reliability (SMT reliability) is the probability that a specified vertex can reach every other vertex. This paper derives a new topological formula for the SMT reliability of probabilistic networks. The formula generates only non-cancelling terms. The non-cancelling terms in the reliability expression correspond one-to-one with the acyclic t-subgraphs of the network. An acyclic t-subgraph is an acyclic graph in which every link is in at least one spanning rooted tree of the graph. The sign to be associated with each term is easily computed by counting the vertices and links in the corresponding subgraph. Overall reliability is the probability that every vertex can reach every other vertex in the network. For an undirected network, it is shown the SMT reliability is equal to the overall reliability. The formula is general and applies to networks containing directed or undirected links. Furthermore link failures in the network can be s-dependent. An algorithm is presented for generating all acyclic t-subgraphs and computing the reliability of the network. The reliability expression is obtained in symbolic factored form.     

The most reliable data-path transmission

This paper examines the problem of transmitting a given amount of data along a single path from a designated source to a designated target in a directed network so that the reliability of the transmission is maximum. In this routing problem, the subpaths of an optimal path are not necessarily optimal. This complicates the process of selecting a path along which the data-transmission is completed in minimum time. A polynomial-time algorithm is presented which guarantees an optimal solution. On acyclic networks with interconnections that operate with the same reliability, another polynomial time algorithm is presented that computes the best route for each possible value of data. This is a useful pre-computation when different amounts of data need to be transmitted at different time periods     

A new formula and an algorithm for reliability analysis of networks

In 1978, Satyanarayana and Prabhakar (SP) proposed a new topological formula for the source-to-terminal (ST) reliability of complex networks. The formula generates only non-cancelling terms of the reliability expression which correspond one-to-one with the p-acyclic subgraphs of the given network. Based on the concept of neutral sequences in acyclic graphs, a powerful SP algorithm was presented for generating all p-acyclic subgraphs and computing the ST reliability of the network. Combining an inclusion-exclusion algorithm with a sum of disjoint products algorithm, we introduce a new topological formula which includes the SP formulas as a special case. A new efficient algorithm which has all features of the SP algorithm is proposed. In general, the reliability expressions obtained by this algorithm are more compact than the ones obtained by the SP algorithm.     

Combined algorithm for the essential graph of Bayesian network structures

Learning Bayesian network structure is one of the most important branches in Bayesian network. The most popular graphical representative of a Bayesian network structure is an essential graph. This paper shows a combined algorithm according to the three rules for finding the essential graph of a given directed acyclic graph. Moreover, the complexity and advantages of this combined algorithm over others are also discussed. The aim of this paper is to present the proof of the correctness of the combined algorithm.     

Some reliability routing problems in an acyclic directed network with stochastic terminal node

This paper considers a stochastic acyclic directed network in which the origin and the final destination nodes are fixed but the process may terminate at random on any intermediate node. Nodes are perfect but the links are assumed to be in one of the two states-good or bad. Problems concerning expected maximum reliability routes have been considered.     

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.     

分层异构信号处理平台调度方法研究

异构多处理器的高效性和可靠性能够满足日趋复杂的信号处理任务需求,因此分层异构系统已成为信号处理平台的发展趋势.为提高平台强实时性并解决高吞吐量的问题,文中对分层异构信号处理平台的软硬件模块及架构进行了研究,并采用有向无环图对组件任务及硬件资源进行建模.将已提出的调度算法按照任务类型、调度目标、调度过程和研究方法进行分类...     

New Topological Formula and Rapid Algorithm for Reliability Analysis of Complex Networks

Part I derives a new topological formula for the terminalpair reliability of complex networks. The formula generates only non-cancelling terms. The non-cancelling terms in the reliability expression correspond one-to-one with the acyclic subgraphs of the given probabilistic graph. Part II introduces the concept of neutral sequences in acyclic graphs; several of their important properties are established. Based on these results a powerful algorithm for generating the reliability expression is presented. The reliability expression is obtained in symbolic factored form. Examples indicate that the present algorithm is appreciably faster than earlier methods. The properties of cyclic and acyclic graphs established in this paper are significant new results in the theory of digraphs and have further ramifications and wider application than in reliability.