Bibtex, reliability and network (in progress)

Title:	Network Reliability
Authors:	Ball, Michael O. Colbourn, Charles J. Provan, J.S.
Department/Program:	ISR
Type:	Technical Report
Keywords:	algorithms, combinatorics, computational complexity, graph theory, reliability, network reliability, networks, Systems Integration
Issue Date:	1992
Series/Report no.:	ISR; TR 1992-74
Abstract:	This paper provides a detailed review of the state of the art in the field of network reliability analysis. The primary model treated is a stochastic network in which arcs fail randomly and independently with known failure probabilities. The inputs to the basic network reliability analysis problem consist of the network and a failure probability for each are in the network. The output is some measure of the reliability of the network. The reliability measures treated most extensively in this paper are: the two terminal measure, the probability that there exists a path between two specified nodes; the all-terminal measure the probability that the network is connected and the k-terminal measure, the probability that a specified node subset, K, is connected. In all cases the results concerning each problem's computational complexity, exact algorithms, analytic bounds and Monte Carlo methods are covered. The paper also treats more complex reliability measures including performability measures and stochastic shortest path, max flow and PERT problems. A discussion is provided on applications and using the techniques covered in practice.
URI:	http://hdl.handle.net/1903/5255
Appears in Collections:	Institute for Systems Research Technical Reports

@ARTICLE{4335422,
author={Ball, M.O.},
journal={Reliability, IEEE Transactions on},
title={Computational Complexity of Network Reliability Analysis: An Overview},
year={1986},
volume={35},
number={3},
pages={230-239},
abstract={This paper presents an overview of results related to the computational complexity of network reliability analysis problems. Network reliability analysis problems deal with the determination of reliability measures for stochastic networks. We show how these problems are related to the more familiar computational network problems of recognizing certain subnetworks, finding optimal subnetworks, and counting certain subnetworks. We use these relationships to show that the k-terminal, the 2-terminal, and the all-terminal network reliability analysis problems are at least as hard as the renowned set of computationally difficult problems, NP-Complete. Finally, we discuss the impact of these results on how one should approach problem solving in this area.},
keywords={Algorithm design and analysis;Computational complexity;Computer network reliability;Computer networks;Educational institutions;Graph theory;Problem-solving;Reliability theory;Seismic measurements;Stochastic processes},
doi={10.1109/TR.1986.4335422},
ISSN={0018-9529},}



@INPROCEEDINGS{12999,
author={Ray, G. A. and Dunsmore, J. J.},
booktitle={INFOCOM '88. Networks: Evolution or Revolution, Proceedings. Seventh Annual Joint Conference of the IEEE Computer and Communcations Societies, IEEE},
title={Reliability of network topologies},
year={1988},
pages={842-850},
abstract={The authors present some analytical results which can be used to compute network reliability. Some simple techniques to make asymptotic approximations based on parameters of the network topology are derived. Explicit reliability formulae are computed for four network topologies, including the star and counterrotating ring. Actual manufacturer's data and failure models for laser diodes and LEDs are used to compare the effects of transmitter reliability on the whole network.<>},
keywords={computer networks;graph theory;network topology;reliability;LAN;LEDs;asymptotic approximations;counterrotating ring;failure models;laser diodes;network reliability;network topologies;network topology;reliability formulae;star topology;transmitter reliability;Communication networks;Computer aided manufacturing;Computer network reliability;Computer networks;Light emitting diodes;Network topology;Optical transmitters;Reliability theory;Telecommunication network reliability;Virtual manufacturing},
doi={10.1109/INFCOM.1988.12999},}

@ARTICLE{5220476,
author={Abraham, J.A.},
journal={Reliability, IEEE Transactions on},
title={An Improved Algorithm for Network Reliability},
year={1979},
volume={R-28},
number={1},
pages={58-61},
abstract={Boolean algebra has been used to find the probability of communication between a pair of nodes in a network by starting with a Boolean product corresponding to simple paths between the pair of nodes and making them disjoint (mutually exclusive). A theorem is given, the use of which enables the disjoint products to be found much faster than by existing methods. An algorithm and results of its implementation on a computer are given. Comparisons with existing methods show the usefulness of the algorithm for large networks.},
keywords={Algorithm design and analysis;Boolean algebra;Computer network reliability;Computer networks;Ducts;Fault trees;Telecommunication network reliability;Boolean expressions;Disjoint products;Reliability algorithm;Terminalpair reliability},
doi={10.1109/TR.1979.5220476},
ISSN={0018-9529},}