摘要:

AbstractDouble loop networks have been intensively studied as interconnecting networks. However, the reliability analysis of such networks has hit a snag since the usual measure of reliability, the graph connectivity, is completely powerless as all double loops, if connected, are 2‐connected. Recently, Hwang and Li introduced a new analysis by partitioning cutsets into isolated and nonisolated ones and gave results on both types. Along the same line, we extent their results to the survival reliability model by showing that when each node fails independently with a very small probability,G(1, 1 + [n/2]) is the most reliable connected double loop network except whenn= 3 and 9, in which caseG(1, 2) is the most reliable. ©1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230502

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractWe present an on‐line distributed reconfiguration algorithm for finding a new maximum matching incrementally after some nodes have failed. Our algorithm is deadlock‐free and, withkfailures, maintains at leastM–kmatching pairs during the reconfiguration process, whereMis the size of the original maximum matching. The algorithm tolerates failures that occur during reconfiguration. The worst‐case reconfiguration time isO(kmin(|A|, |B|)) afterkfailures, whereAandBare the node sets, but simulations show that the average‐case reconfiguration time is much better. The algorithm is also simple enough to be implemented in hardware. ©1993 by John Wiley

ISSN:0028-3045    

DOI:10.1002/net.3230230503

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractIn this paper, we introduce a construction that produces graphs, calledE‐graphs, by replacing the edges in a core graph with a copy of a given graph. These graphs are generalizations of several graphs that have recently been presented as models for network designs, including theG‐network and its extensions. We discuss several invariant properties of these graphs with emphasis on those of interest in network design, such as number of edges, diameter, and domination number. ©1993 by John Wiley&Sons,

ISSN:0028-3045    

DOI:10.1002/net.3230230504

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractBroadcast is the task of transmitting a message from any node in a network to all other nodes in the network. A minimal broadcast network (mbn) is a communication network in which a message can be broadcasted in minimum time regardless of the originator. In this article, a new method to construct such mbn's is presented. The new method improves the best known upper bounds on the minimum number of edges in mbn's for most cases. ©1993 by John Wiley&Sons, Inc

ISSN:0028-3045    

DOI:10.1002/net.3230230505

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractA belief network is a graphical representation of the underlying probabilistic relationships in a complex system. Belief networks have been employed as a representation of uncertain relationships in computer‐based diagnostic systems. These diagnostic systems provide assistance by assigning likelihoods to alternative explanatory hypotheses in response to a set of findings or observations. Approximation algorithms have been used to compute likelihoods of hypotheses in large networks. We analyze the performance of leading Monte Carlo approximation algorithms for computing posterior probabilities in belief networks. The analysis differs from earlier attempts to characterize the behavior of simulation algorithms in our explicit use of Bayesian statistics: We update a probability distribution over target probabilities of interest with information from randomized trials. For real ϵ, δ<1 and for a probabilistic inference Pr[x|e], the output of an inference approximation algorithm in an (ϵ, δ)‐estimateof Pr[x|e] if with probability at least 1 – δ the output is within relative error ϵ of Pr[x|e]. We construct a stopping rule for the number of simulations required bylogic sampling, randomized approximation schemes, andlikelihood weightingto provide (ϵ, δ)‐estimates of Pr[x|e]. With Probability 1 – δ, the stopping rule isoptimalin the sense that the algorithm performs the minimum number of required simulations. We prove that our stopping rules are insensitive to the prior probability distribution on Pr[x|e]. ©1993 by J

ISSN:0028-3045    

DOI:10.1002/net.3230230506

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230230501

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY