SPECIAL ISSUE ARTICLE
Network reliability: Heading out on the highway
Jason I. Brown,
Charles J. Colbourn,
Danielle Cox,
Christina Graves,
Lucas Mol,
Corresponding Author
Jason I. Brown
Department of Mathematics and Statistics, Dalhousie University, Halifax, Canada
Correspondence
Jason I. Brown, Department of Mathematics and Statistics, Dalhousie University, 6316 Coburg Road, PO Box 15000, Halifax, Nova Scotia, Canada B3H 4R2.
Email: [email protected]
Search for more papers by this authorCharles J. Colbourn
School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe, Arizona, USA
Search for more papers by this authorDanielle Cox
Department of Mathematics, Mount Saint Vincent University, Halifax, Canada
Search for more papers by this authorChristina Graves
Department of Mathematics, University of Texas at Tyler, Tyler, Texas, USA
Search for more papers by this authorLucas Mol
Department of Mathematics and Statistics, University of Winnipeg, Winnipeg, Canada
Search for more papers by this authorJason I. Brown,
Charles J. Colbourn,
Danielle Cox,
Christina Graves,
Lucas Mol,
Corresponding Author
Jason I. Brown
Department of Mathematics and Statistics, Dalhousie University, Halifax, Canada
Correspondence
Jason I. Brown, Department of Mathematics and Statistics, Dalhousie University, 6316 Coburg Road, PO Box 15000, Halifax, Nova Scotia, Canada B3H 4R2.
Email: [email protected]
Search for more papers by this authorCharles J. Colbourn
School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe, Arizona, USA
Search for more papers by this authorDanielle Cox
Department of Mathematics, Mount Saint Vincent University, Halifax, Canada
Search for more papers by this authorChristina Graves
Department of Mathematics, University of Texas at Tyler, Tyler, Texas, USA
Search for more papers by this authorLucas Mol
Department of Mathematics and Statistics, University of Winnipeg, Winnipeg, Canada
Search for more papers by this authorFunding information: Natural Sciences and Engineering Research Council of Canada, RGPIN 2017-04401; RGPIN 2018-05227
Abstract
A variety of probabilistic notions of network reliability of graphs and digraphs have been proposed and studied since the early 1950s. Although grounded in the engineering and logistics of network design and analysis, the research also spans pure and applied mathematics, with connections to areas as diverse as combinatorics and graph theory, combinatorial enumeration, optimization, probability theory, real and complex analysis, algebraic topology, commutative algebra, the design and analysis of algorithms, and computational complexity. In this paper we describe the landscape of various notions of network reliability, the roads well traveled, and some that appear likely to lead to meaningful and important journeys.
REFERENCES
- 1H.M. AboElFotoh and C.J. Colbourn, Efficient algorithms for computing the reliability of permutation and interval graphs, Networks 20 (1990), 883–898.
- 2P. Adasme, R. Andrade, M. Letournel, and A. Lisser, Stochastic maximum weight forest problem, Networks 65 (2015), 289–305.
- 3K. Adiprasito, J. Huh, and E. Katz, Hodge theory for combinatorial geometries, Ann. Math. 188 (2018), 381–452.
- 4A. Agrawal and R.E. Barlow, A survey of network reliability and domination theory, Oper Res 32 (1984), 478–492.
- 5A. Agrawal and A. Satyanarayana, Network reliability analysis using 2-connected digraph reductions, Networks 15 (1985), 239–256.
- 6C. Alexopoulos and G.S. Fishman, Characterizing stochastic flow networks using the Monte Carlo method, Networks 21 (1991), 775–798.
- 7C. Alexopoulos and G.S. Fishman, Sensitivity analysis in stochastic flow networks using the Monte Carlo method, Networks 23 (1993), 605–621.
- 8A.T. Amin, K.T. Siegrist, and P.J. Slater, On the nonexistence of uniformly optimal graphs for pair-connected reliability, Networks 21 (1991), 359–368.
- 9A.T. Amin, K.T. Siegrist, and P.J. Slater, On uniformly optimally reliable graphs for pair-connected reliability with vertex failures, Networks 23 (1993), 185–193.
- 10T. Anazawa, T. Kodera, and M. Jimbo, Optimum requirement spanning trees and reliability of tree networks, Networks 34 (1999), 122–131.
- 11G. Andreatta and L. Romeo, Stochastic shortest paths with recourse, Networks 18 (1988), 193–204.
- 12Y.P. Aneja and K.P.K. Nair, Maximal expected flow in a network subject to arc failures, Networks 10 (1980), 45–57.
- 13K. Archer, C. Graves, and D. Milan, Classes of uniformly most reliable graphs for all-terminal reliability, Discrete Appl. Math. 267 (2019), 12–29.
- 14A. Atamtürk and A. Bhardwaj, Network design with probabilistic capacities, Networks 71 (2018), 16–30.
- 15C. Balbuena, P. García-Vázquez, and X. Marcote, Reliability of interconnection networks modeled by a product of graphs, Networks 48 (2006), 114–120.
- 16M.O. Ball, Complexity of network reliability computations, Networks 10 (1980), 153–165.
- 17M.O. Ball, C.J. Colbourn, and J.S. Provan, “ Network reliability,” Network Models, Handbooks Oper. Res. Management Sci., vol. 7, North-Holland, Amsterdam, 1995, pp. 673–762.
- 18M.O. Ball, J.N. Hagstrom, and J.S. Provan, Threshold reliability of networks with small failure sets, Networks 25 (1995), 101–115.
- 19M.O. Ball and G.L. Nemhauser, Matroids and a reliability analysis problem, Math. Oper. Res. 4 (1979), 132–143.
- 20M.O. Ball and J.S. Provan, Bounds on the reliability polynomial for shellable independence systems, SIAM J. Algebraic Discrete Methods 3 (1982), 166–181.
- 21M.O. Ball and J.S. Provan, Calculating bounds on reachability and connectedness in stochastic networks, Networks 13 (1983), 253–278.
- 22M.O. Ball, J.S. Provan, and D.R. Shier, Reliability covering problems, Networks 21 (1991), 345–357.
- 23R.E. Barlow and F. Proschan, Statistical Theory of Reliability and Life Testing, Holt, Rinehart and Winston, New York, London, 1975.
- 24D. Bauer, F. Boesch, C. Suffel, and R. Tindell, Combinatorial optimization problems in the analysis and design of probabilistic networks, Networks 15 (1985), 257–271.
- 25
F. Beichelt and P. Tittmann, Reliability and Maintenance—Networks and Systems, Boca Raton, FL: CRC Press, 2012.
10.1201/b12095 Google Scholar
- 26H. Bertrand, O. Goff, C. Graves, and M. Sun, On uniformly most reliable two-terminal graphs, Networks 72 (2018), 200–216.
- 27D.J. Bertsimas, The probabilistic minimum spanning tree problem, Networks 20 (1990), 245–275.
- 28D. Bienstock, An algorithm for reliability analysis of planar graphs, Networks 16 (1986), 411–422.
- 29Z.W. Birnbaum and J.D. Esary, Modules of coherent binary systems, J. Soc. Indust. Appl. Math. 13 (1965), 444–462.
- 30Z.W. Birnbaum, J.D. Esary, and S.C. Saunders, Multicomponent systems and structures and their reliability, Technometrics 3 (1961), 55–77.
- 31L.D. Bodin, Approximations to system reliability using a modular decomposition, Technometrics 12 (1970), 335–344.
- 32F.T. Boesch, On unreliability polynomials and graph connectivity in reliable network synthesis, J Graph Theory 10 (1986), 339–352.
- 33F.T. Boesch, Synthesis of reliable networks—A survey, IEEE Trans. Reliab. 35 (1986), 240–246.
- 34F.T. Boesch, F. Harary, and J.A. Kabell, Graphs as models of communication network vulnerability: Connectivity and persistence, Networks 11 (1981), 57–63.
- 35F.T. Boesch, X. Li, and C.L. Suffel, On the existence of uniformly optimally reliable networks, Networks 21 (1991), 181–194.
- 36F.T. Boesch, A. Satyanarayana, and C.L. Suffel, Least reliable networks and the reliability domination, IEEE Trans. Commun. 38 (1990), 2004–2009.
- 37F.T. Boesch, A. Satyanarayana, and C.L. Suffel, A survey of some network reliability analysis and synthesis results, Networks 54 (2009), 99–107.
- 38E. Boros, Y. Crama, O. Ekin, P. Hammer, T. Ibaraki, and A. Kogan, Boolean normal forms, shellability, and reliability computations, SIAM J Discrete Math 13 (2000), 212–226.
- 39G.E.P. Box, Science and statistics, J Am Stat Assoc 71 (1976), 791–799.
- 40S.D. Boyles and S.T. Waller, A mean-variance model for the minimum cost flow problem with stochastic arc costs, Networks 56 (2010), 215–227.
- 41T.B. Brecht and C.J. Colbourn, Improving reliability bounds in computer networks, Networks 16 (1986), 369–380.
- 42T.B. Brecht and C.J. Colbourn, Multiplicative improvements in network reliability bounds, Networks 19 (1989), 521–529.
- 43F. Brenti, G.F. Royle, and D.G. Wagner, Location of zeros of chromatic and related polynomials of graphs, Canad. J. Math. 46 (1994), 55–80.
- 44D.B. Brown, A computerized algorithm for determining the reliability of redundant configurations, IEEE Trans. Reliab. R-20 (1971), 121–124.
- 45J.I. Brown and B. Cameron, On the unimodality of independence polynomials of very well-covered graphs, Discrete Math. 341 (2018), 1138–1143.
- 46J.I. Brown and C.J. Colbourn, Roots of the reliability polynomials, SIAM J. Discrete Math. 5 (1992), 571–585.
- 47J.I. Brown, C.J. Colbourn, and J.S. Devitt, Network transformations and bounding network reliability, Networks 23 (1993), 1–17.
- 48J.I. Brown, C.J. Colbourn, and R.J. Nowakowski, Chip firing and all-terminal network reliability bounds, Discrete Optim 6 (2009), 436–445.
- 49J.I. Brown and D. Cox, The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane, Discrete Math. 309 (2009), 5043–5047.
- 50J.I. Brown and D. Cox, Nonexistence of optimal graphs for all terminal reliability, Networks 63 (2014), 146–153.
- 51J.I. Brown and D. Cox, Inflection points of reliability polynomials are dense in [0,1], Networks 67 (2016), 266–269.
- 52J.I. Brown, D. Cox, and R. Ehrenborg, The average reliability of a graph, Discrete Appl. Math. 177 (2014), 19–33.
- 53J.I. Brown and C.D.C. DeGagné, On the reliability roots of simplicial complexes and matroids, Discrete Math. 342 (2019), 2356–2370.
- 54J. I. Brown and C. D. C. DeGagné. Roots of two-terminal reliability polynomials, Networks, 2021, in press.
- 55J.I. Brown and K. Dilcher, On the roots of strongly connected reliability polynomials, Networks 54 (2009), 108–116.
- 56J.I. Brown, C.A. Hickman, and R.J. Nowakowski, The independence fractal of a graph, J. Combin. Theory Ser. B 87 (2003), 209–230.
- 57J.I. Brown, Y. Koç, and R.E. Kooij, Inflection points for network reliability, Telecommun. Syst. 56 (2014), 79–84.
- 58J.I. Brown and X. Li, The strongly connected reliability of complete digraphs, Networks 45 (2005), 165–168.
- 59J.I. Brown and X. Li, Uniformly optimal digraphs for strongly connected reliability, Networks 49 (2007), 145–151.
- 60J.I. Brown and L. Mol, On the roots of the node reliability polynomial, Networks 68 (2016), 238–246.
- 61J.I. Brown and L. Mol, On the roots of all-terminal reliability polynomials, Discrete Math. 340 (2017), 1287–1299.
- 62J.I. Brown and L. Mol, The shape of node reliability, Discrete Appl. Math. 238 (2018), 41–55.
- 63A.L. Buchsbaum and M. Mihail, Monte Carlo and Markov chain techniques for network reliability and sampling, Networks 25 (1995), 117–130.
- 64B. Büke, J.C. Smith, and S. Thomas, On a random walk survivability problem with arc failures and memory, Networks 66 (2015), 67–86.
- 65J.A. Buzacott, A recursive algorithm for finding reliability measures related to the connection of nodes in a graph, Networks 10 (1980), 311–327.
- 66J.A. Buzacott, A recursive algorithm for directed-graph reliability, Networks 13 (1983), 241–246.
- 67J.A. Buzacott, Node partition formula for directed graph reliability, Networks 17 (1987), 227–240.
- 68E. Canale, H. Cancela, F. Robledo, P. Romero, and P. Sartor, Diameter constrained reliability: Complexity, distinguished topologies and asymptotic behavior, Networks 66 (2015), 296–305.
- 69E. Canale, P. Romero, and G. Rubino, Factorization and exact evaluation of the source-terminal diameter-constrained reliability, Networks 70 (2017), 283–291.
- 70M. Carey and C. Hendrickson, Bounds on expected performance of networks with links subject to failure, Networks 14 (1984), 439–456.
- 71R. Cerulli, M. Gentili, and A. Raiconi, Maximizing lifetime and handling reliability in wireless sensor networks, Networks 64 (2014), 321–338.
- 72S.-C. Chang and R. Shrock, Reliability polynomials and their asymptotic limits for families of graphs, J. Stat. Phys. 112 (2003), 1019–1077.
- 73R.M. Chavez and G.F. Cooper, A randomized approximation algorithm for probabilistic inference on Bayesian belief networks, Networks 20 (1990), 661–685.
- 74M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B 97 (2007), 350–357.
- 75C.J. Colbourn, The Combinatorics of Network Reliability, Oxford Univ. Press, Oxford, 1987.
- 76 C.J. Colbourn, “ Some open problems for reliability polynomials,” Proceedings of the 24th Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Congr Numer., vol. 93, Canada: Winnipeg, 1993, pp. 187–202.
- 77C.J. Colbourn and D.D. Harms, Bounding all-terminal reliability in computer networks, Networks 18 (1988), 1–12.
- 78G.A. Corea and V.G. Kulkarni, Shortest paths in stochastic networks with arc lengths having discrete distributions, Networks 23 (1993), 175–183.
- 79D. Cox. On Network reliability. PhD thesis, Dalhousie University, 2013.
- 80M.S. Daly and C. Alexopoulos, State-space partition techniques for multiterminal flows in stochastic networks, Networks 48 (2006), 90–111.
- 81T. Egeland and A.B. Huseby, On dependence and reliability computations, Networks 21 (1991), 521–545.
- 82E.S. El-Mallah, Algorithms for K-terminal reliability problems with node failures, Networks 22 (1992), 369–384.
- 83P. Erdös and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297.
- 84P. Erdös and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61.
- 85J.D. Esary and F. Proschan, Coherent structures of non-identical components, Technometrics 5 (1963), 191–209.
- 86J.D. Esary and F. Proschan, Relationship between system failure rate and component failure rates, Technometrics 5 (1963), 183–189.
- 87T. Evans and D. Smith, Optimally reliable graphs for both edge and vertex failures, Networks 16 (1986), 199–204.
- 88T.R. Farley and C.J. Colbourn, Multiterminal resilience for series-parallel networks, Networks 50 (2007), 164–172.
- 89G.S. Fishman, A Monte Carlo sampling plan for estimating reliability parameters and related functions, Networks 17 (1987), 169–186.
- 90H. Frank, Shortest paths in probabilistic graphs, Oper Res 17 (1969), 583–599.
- 91H. Frank and W. Chou, Network properties of the ARPA computer network, Networks 4 (1974), 213–239.
10.1002/net.3230040303 Google Scholar
- 92 H. Frank and I.T. Frisch, Communication, Transmission and Transportation Networks, Ann Arbor, MI: Addison-Wesley, 1971.
- 93H. Frank, I.T. Frisch, R.M. Van Slyke, and W. Chou, Optimal design of centralized computer networks, Networks 1 (1971), 43–57.
10.1002/net.3230010105 Google Scholar
- 94H. Frank and S. Hakimi, Probabilistic flows through a communication network, IEEE Trans. Circuit Theory 12 (1965), 413–414.
10.1109/TCT.1965.1082452 Google Scholar
- 95H. Frank, R.E. Kahn, and L. Kleinrock, Computer communication network design: Experience with theory and practice, Networks 2 (1972), 135–166.
10.1002/net.3230020205 Google Scholar
- 96O. Frank and W. Gaul, On reliability in stochastic graphs, Networks 12 (1982), 119–126.
- 97I.T. Frisch, The early days of Networks, Networks 37 (2001), 1–7.
- 98Y. Fu and S.S. Yau, A note on the reliability of communication networks, J. Soc. Indust. Appl. Math. 10 (1962), 469–474.
- 99S. Geetha and K.P.K. Nair, On stochastic spanning tree problem, Networks 23 (1993), 675–679.
- 100I.B. Gertsbakh and Y. Shpungin, Network Reliability and Resilience, Springer, Berlin, 2011.
10.1007/978-3-642-22374-7 Google Scholar
- 101E.N. Gilbert, Random graphs, Ann. Math. Statist. 30 (1959), 1141–1144.
- 102N. Goldberg, S. Leyffer, and I. Safro, Optimal response to epidemics and cyber attacks in networks, Networks 66 (2015), 145–158.
- 103O. Goldschmidt, P. Jaillet, and R. LaSota, On reliability of graphs with node failures, Networks 24 (1994), 251–259.
- 104D. Gómez-Pérez, J. Gutierrez, and Á. Ibeas, Connectedness of finite distance graphs, Networks 60 (2012), 204–209.
- 105C. Graves, Inflection points of coherent reliability polynomials, Australas. J. Combin. 49 (2011), 111–126.
- 106C. Graves and D. Milan, Reliability polynomials having arbitrarily many inflection points, Networks 64 (2014), 1–5.
- 107D. Gross and J.T. Saccoman, Uniformly optimally reliable graphs, Networks 31 (1998), 217–225.
- 108J.N. Hagstrom, Note on independence of arcs in antiparallel for network flow problems, Networks 14 (1984), 567–570.
- 109J.N. Hagstrom, Computational complexity of PERT problems, Networks 18 (1988), 139–147.
- 110J.N. Hagstrom, Computing the probability distribution of project duration in a PERT network, Networks 20 (1990), 231–244.
- 111J.N. Hagstrom, Directed network reliability: Domination and computing coefficients of the success-marginal expansion, Networks 20 (1990), 65–78.
- 112J.N. Hagstrom, Computing rooted communication reliability in an almost acyclic digraph, Networks 21 (1991), 581–593.
- 113T. Hailperin, Best possible inequalities for the probability of a logical function of events, Amer Math Monthly 72 (1965), 343–359.
- 114S.L. Hakimi and A.T. Amin, On the design of reliable networks, Networks 3 (1973), 241–260.
10.1002/net.3230030304 Google Scholar
- 115E. Hänsler, A fast recursive algorithm to calculate the reliability of a communication network, IEEE Trans. Commun. 20 (1972), 637–640.
- 116E. Hänsler, G.K. McAuliffe, and R.S. Wilkov, Exact calculation of computer network reliability, Networks 4 (1974), 95–112.
10.1002/net.3230040202 Google Scholar
- 117D.D. Harms and C.J. Colbourn, Renormalization of two-terminal reliability, Networks 23 (1993), 289–297.
- 118K.C. Hastings and D.R. Shier, Algebraic methods applied to shortest path and maximum flow problems in stochastic networks, Networks 61 (2013), 117–127.
- 119X.D. Hu, F.K. Hwang, and W.-C.W. Li, Most reliable double loop networks in survival reliability, Networks 23 (1993), 451–458.
- 120J. Huh, h-Vectors of matroids and logarithmic concavity, Adv. Math. 270 (2015), 49–59.
- 121J. Huh and E. Katz, Log-concavity of characteristic polynomials and the Bergman fan of matroids, Math. Ann. 354 (2012), 1103–1116.
- 122A.B. Huseby, Domination theory and the Crapo β-invariant, Networks 19 (1989), 135–149.
- 123F.K. Hwang, P.E. Wright, and X.D. Hu, Exact reliabilities of most reliable double-loop networks, Networks 30 (1997), 81–90.
- 124I. M. Jacobs. Connectivity in probabilistic graphs. Technical Report 356, Electronics Research Laboratory, MIT, 1959.
- 125P.A. Jensen and M. Bellmore, An algorithm to determine the reliability of a complex system, IEEE Trans. Reliab. R-18 (1969), 169–174.
- 126R. Johnson, Network reliability and acyclic orientations, Networks 14 (1984), 489–505.
- 127R.M. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975), 45–68.
10.1002/net.1975.5.1.45 Google Scholar
- 128R.M. Karp and M. Luby, Monte Carlo algorithms for the planar multiterminal network reliability problem, J Complexity 1 (1985), 45–64.
10.1016/0885-064X(85)90021-4 Google Scholar
- 129G.O.H. Katona, “ A theorem of finite sets,” Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 187–207.
- 130G.O.H. Katona and W.A. Woyczyński, Optimization of the reliability polynomial in presence of mediocre elements, Networks 23 (1993), 327–332.
- 131V.A. Kaustov, Y.I. Litvak, and I.A. Ushakov, The computational effectiveness of reliability estimates by the method of nonedge-intersecting chains and cuts, Izv. Akad. Nauk SSSR Tekhn. Kibernet. 24 (1986), 70–73.
- 132A.K. Kelmans, On certain optimal problems in the theory of reliability of information transmission systems, Automat. Remote Control 25 (1964), 661–667.
- 133A.K. Kelmans, Connectivity of probabilistic networks, Automat. Remote Control 3 (1967), 444–460.
- 134A.K. Kelmans, Bounds on the probability characteristics of random graphs, Avtomat. Telemeh. 32 (1970), 130–137.
- 135A.K. Kelmans, On graphs with randomly deleted edges, Acta Math. Acad. Sci. Hung. 37 (1981), 197–214.
- 136A. Kershenbaum and R.M. Van Slyke, Recursive analysis of network reliability, Networks 3 (1973), 81–94.
10.1002/net.3230030107 Google Scholar
- 137E. Kranakis, M. Paquette, and A. Pelc, The diameter and connectivity of networks with random dependent faults, Networks 56 (2010), 103–115.
- 138J.B. Kruskal, “ The number of simplices in a complex,” Mathematical Optimization Techniques, Univ. California Press, Berkeley, CA, 1963, pp. 251–278.
10.1525/9780520319875-014 Google Scholar
- 139V.G. Kulkarni, Shortest paths in networks with exponentially distributed arc lengths, Networks 16 (1986), 255–274.
- 140V.G. Kulkarni, Minimal spanning trees in undirected networks with exponentially distributed arc weights, Networks 18 (1988), 111–124.
- 141T. Lange, M. Reinwardt, and P. Tittmann, A recursive formula for the two-edge connected and biconnected reliability of a complete graph, Networks 69 (2017), 408–414.
- 142C.Y. Lee, Analysis of switching networks, Bell System Tech. J. 34 (1955), 1287–1315.
- 143L.M. Leemis, M.J. Duggan, J.H. Drew, J.A. Mallozzi, and K.W. Connell, Algorithms to calculate the distribution of the longest path length of a stochastic activity network with continuous activity durations, Networks 48 (2006), 143–165.
- 144J. Leggett and S. Bedrosian, Synthesis of reliable networks, IEEE Trans. Circ. Theory 16 (1969), 384–385.
10.1109/TCT.1969.1082978 Google Scholar
- 145A.B. Lehman, Wye-Delta transformation in probabilistic networks, J. Soc. Indust. Appl. Math. 11 (1963), 773–805.
- 146M. Lenz, The f-vector of a representable-matroid complex is log-concave, Adv. Appl. Math. 51 (2013), 543–545.
- 147L.L. Levy and A.H. Moore, A Monte Carlo technique for obtaining system reliability confidence limits from component test data, IEEE Trans. Reliab. R-16 (1967), 69–72.
- 148Q. Li and Q. Li, Reliability analysis of circulant graphs, Networks 31 (1998), 61–65.
- 149D.-R. Liang, R.-H. Jan, and S.K. Tripathi, Reliability analysis of replicated and-or graphs, Networks 29 (1997), 195–203.
- 150G.T. Lingner, T. Politof, and A. Satyanarayana, A forbidden minor characterization and reliability of a class of partial 4-trees, Networks 25 (1995), 139–146.
- 151S. Liu, K.-H. Cheng, and X. Liu, Network reliability with node failures, Networks 35 (2000), 109–117.
- 152M.V. Lomonosov and V.P. Polesskii, An upper bound for the reliability of information networks, Probl. Inf. Transm. 7 (1971), 337–339.
- 153M.V. Lomonosov and V.P. Polesskii, Lower bound of network reliability, Probl. Inf. Transm. 8 (1972), 118–123.
- 154X. Marcote, C. Balbuena, and J. Fàbrega, Connectedness of digraphs and graphs under constraints on the conditional diameter, Networks 45 (2005), 80–87.
- 155E. Mata-Montero, Resilience of partial k-tree networks with edge and node failures, Networks 21 (1991), 321–344.
- 156M. Michelen and J. Sahasrabudhe, Central limit theorems from the roots of probability generating functions, Adv. Math. 358 (2019), 106840.
- 157H. Mine, Reliability of a physical system, IEEE Trans. Circ. Theory 6 (1959), 138–151.
10.1109/TCT.1959.1086604 Google Scholar
- 158E.F. Moore and C.E. Shannon, Reliable circuits using less reliable relays. I, II, J. Franklin Inst. 262(191–208) (1956), 281–297.
10.1016/0016-0032(56)90044-8 Google Scholar
- 159F. Moskowitz, The analysis of redundancy networks, Trans. Am. Inst. Electr. Eng. Part I: Commun. Electron. 77 (1958), 627–632.
- 160C. Murat and V.T. Paschos, The probabilistic longest path problem, Networks 33 (1999), 207–219.
- 161W. Myrvold, K.H. Cheung, L.B. Page, and J.E. Perry, Uniformly most reliable networks do not always exist, Networks 21 (1991), 417–419.
- 162H. Nagamochi and T. Ibaraki, Maximum flows in probabilistic networks, Networks 21 (1991), 645–666.
- 163L.D. Nel and C.J. Colbourn, Combining Monte Carlo estimates and bounds for network reliability, Networks 20 (1990), 277–298.
- 164A.C. Nelson, J.R. Batts, and R.L. Beadles, A computer program for approximating system reliability, IEEE Trans. Reliab. R-19 (1970), 61–65.
- 165E.M. Neufeld and C.J. Colbourn, The most reliable series-parallel networks, Networks 15 (1985), 27–32.
- 166F. Pan and D.P. Morton, Minimizing a stochastic maximum-reliability path, Networks 52 (2008), 111–119.
- 167H. Pérez-Rosés, Sixty years of network reliability, Math. Comput. Sci. 12 (2018), 275–293.
- 168L. Petingi, J.T. Saccoman, and L. Schoppmann, Uniformly least reliable graphs, Networks 27 (1996), 125–131.
- 169N. Pippenger, “ Developments in “The synthesis of reliable organisms from unreliable components”,” The legacy of John von Neumann (Hempstead, NY, 1988). Proc. Sympos. Pure Math., vol. 50, Amer. Math. Soc., Providence, RI, 1990, pp. 311–324.
10.1090/pspum/050/1067764 Google Scholar
- 170T. Politof, On a property of cyclic covers of p-graphs, Networks 18 (1988), 51–53.
- 171J.S. Provan, Polyhedral combinatorics and network reliability, Math. Oper. Res. 11 (1986), 36–61.
- 172J.S. Provan, A polynomial-time algorithm to find shortest paths with recourse, Networks 41 (2003), 115–125.
- 173J.S. Provan and M.O. Ball, The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput. 12 (1983), 777–788.
- 174J.S. Provan and L.J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980), 576–594.
- 175K.W. Pullen, A random network model of message transmission, Networks 16 (1986), 397–409.
- 176M. Redmond, A.M. Campbell, and J.F. Ehmke, The most reliable flight itinerary problem, Networks 73 (2019), 325–343.
- 177D. Reich and L. Lopes, The most likely path on series-parallel networks, Networks 58 (2011), 68–80.
- 178M. Roccetti, Reliability analysis of tree-based networks and the application to fault-tolerant VLSI systems, Networks 26 (1995), 217–230.
- 179J. Rodriguez and L. Traldi, (K, j)-domination and (K, j)-reliability, Networks 30 (1997), 293–306.
- 180A. Rosenthal, “ A computer scientist looks at reliability computations,” Reliability and Fault Tree Analysis, R.E. Barlow, J.B. Fussel, and D.D. Singpurwalla (eds), SIAM, New York, 1975, pp. 133–152.
- 181A. Rosenthal, Series-parallel reduction for difficult measures of network reliability, Networks 11 (1981), 323–334.
- 182A. Rosenthal and D. Frisque, Transformations for simplifying network reliability calculations, Networks 7 (1977), 97–111.
- 183G. Royle and A.D. Sokal, The Brown-Colbourn conjecture on zeros of reliability polynomials is false, J. Combin. Theory Ser. B 91 (2004), 345–360.
- 184
A. Rueda and M. Pawlak, “ Pioneers of the reliability theories of the past 50 years,” Annual Symposium Reliability and Maintainability, 2004–RAMS, NJ: Piscataway, 2004, pp. 102–109.
10.1109/RAMS.2004.1285431 Google Scholar
- 185M. Rysz, P.A. Krokhmal, and E.L. Pasiliao, Detecting resilient structures in stochastic networks: A two-stage stochastic optimization approach, Networks 69 (2017), 189–204.
- 186A. Satyanarayana and M.K. Chang, Network reliability and the factoring theorem, Networks 13 (1983), 107–120.
- 187A. Satyanarayana and J.N. Hagstrom, Combinatorial properties of directed graphs useful in computing network reliability, Networks 11 (1981), 357–366.
- 188A. Satyanarayana, L. Schoppmann, and C.L. Suffel, A reliability-improving graph transformation with applications to network reliability, Networks 22 (1992), 209–216.
- 189D.R. Shier, “ Iterative algorithms for calculating network reliability,” Graph Theory with Applications to Algorithms and Computer Science (Kalamazoo, Mich., 1984), Wiley-Intersci. Publ., Wiley, New York, 1985, pp. 741–752.
- 190D.R. Shier, Network Reliability and Algebraic Structures, Oxford Science Publications. The Clarendon Press, Oxford Univ. Press, New York, 1991.
10.1093/oso/9780198533863.001.0001 Google Scholar
- 191D.R. Shier, E.J. Valvo, and R.E. Jamison, Generating the states of a binary stochastic system, Discrete Appl Math 37/38 (1992), 489–500.
- 192D.R. Shier and D.E. Whited, Iterative algorithms for generating minimal cutsets in directed graphs, Networks 16 (1986), 133–147.
- 193D.R. Shier and D.E. Whited, Algebraic methods applied to network reliability problems, SIAM J Algebraic Discrete Methods 8 (1987), 251–262.
10.1137/0608022 Google Scholar
- 194A.W. Shogan, Bounding distributions for a stochastic PERT network, Networks 7 (1977), 359–381.
- 195A.W. Shogan, A decomposition algorithm for network reliability analysis, Networks 8 (1978), 231–251.
- 196A.W. Shogan, Modular decomposition and reliability computation in stochastic transportation networks having cutnodes, Networks 12 (1982), 255–275.
- 197M.L. Shooman, Probabilistic Reliability: An Engineering Approach, McGraw-Hill, New York, 1968.
- 198J. Silva, T. Gomes, D. Tipper, L. Martins, and V. Kounev, An effective algorithm for computing all-terminal reliability bounds, Networks 66 (2015), 282–295.
- 199D.H. Smith and L.L. Doty, On the construction of optimally reliable graphs, Networks 20 (1990), 723–729.
- 200A.D. Sokal, Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions, Combin. Probab. Comput. 10 (2001), 41–77.
- 201J.E. Somers, Maximum flow in networks with a small number of random arc capacities, Networks 12 (1982), 241–253.
- 202E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math Z 27 (1928), 544–548.
- 203N. Spyratos and A. Bowen, A fast algorithm for reliability calculations in sparse networks, Networks 7 (1977), 227–246.
- 204R.P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann N Y Acad Sci 576 (1989), 500–534.
- 205V.E. Stepanov, Combinatorial algebra and random graphs, Teor Verojatnost i Primenen 14 (1969), 393–420.
- 206C. Stivaros and K. Sutner, The intractability of the reliable assignment problem in split networks, Networks 26 (1995), 165–172.
- 207H.J. Strayer and C.J. Colbourn, Consecutive cuts and paths, and bounds on k-terminal reliability, Networks 25 (1995), 165–175.
- 208J.L. Trahan and S. Rai, Reliability evaluation and decision problems in extra shuffle-exchange MINs, Networks 23 (1993), 415–426.
- 209L. Traldi, On the star-delta transformation in network reliability, Networks 23 (1993), 151–157.
- 210I. Ushakov, “ Reliability: Past, present, future,” Recent Advances in Reliability Theory. Statistics for Industry and Technology, N. Limnios and M. Nikulin (eds), Birkhäuser, Boston, MA, 2000.
10.1007/978-1-4612-1384-0_1 Google Scholar
- 211L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979), 410–421.
- 212R.M. Van Slyke, Stochastic aspects of networks, Networks 5 (1975), 97–100.
10.1002/net.1975.5.1.97 Google Scholar
- 213R.M. Van Slyke and H. Frank, Network reliability analysis. Part I, Networks 1 (1971), 279–290.
10.1002/net.3230010307 Google Scholar
- 214R.M. Van Slyke, H. Frank, and A. Kershenbaum, “ Network reliability analysis: Part II,” Reliability and Fault Tree Analysis, R.E. Barlow, J.B. Fussel, and D.D. Singpurwalla (eds), SIAM, New York, 1975, pp. 619–650.
- 215J. von Neumann, “ Probabilistic logics and the synthesis of reliable organisms from unreliable components,” Automata Studies, Annals of Mathematics Studies, No. 34, Princeton Univ. Press, Princeton, NJ, 1956, pp. 43–98.
10.1515/9781400882618-003 Google Scholar
- 216D.G. Wagner, Zeros of reliability polynomials and f-vectors of matroids, Combin. Probab. Comput. 9 (2000), 167–190.
- 217D.K. Wagner, Disjoint (s, t)-cuts in a network, Networks 20 (1990), 361–371.
- 218G. Wang, A proof of Boesch's conjecture, Networks 24 (1994), 277–284.
- 219G. Wang and L. Zhang, The structure of maxλ-min mλ + 1 graphs used in the design of reliable networks, Networks 30 (1997), 231–242.
- 220J. Wang, The β-reliable minimax and maximin location problems on a network with probabilistic weights, Networks 55 (2010), 99–107.
- 221Y. Wang and B.X. Zhu, On the unimodality of independence polynomials of some graphs, Eur. J. Combin. 32 (2011), 10–20.
- 222R.R. Willie, A theorem concerning cyclic directed graphs with applications to network reliability, Networks 10 (1980), 71–78.
- 223R.K. Wood, A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability, Networks 15 (1985), 173–190.
- 224R.K. Wood, Triconnected decomposition for computing K-terminal network reliability, Networks 19 (1989), 203–220.
- 225G. Xue, Linear time algorithms for computing the most reliable source on an unreliable tree network, Networks 30 (1997), 37–45.
- 226J.Y. Assous, First- and second-order bounds on terminal reliability, Networks 16 (1986), 319–329.
- 227C. Yang and J.-M. Xu, Reliability of interconnection networks modeled by Cartesian product digraphs, Networks 52 (2008), 202–205.
- 228E. Zemel, Polynomial algorithms for estimating network reliability, Networks 12 (1982), 439–452.
- 229R. Zenklusen and M. Laumanns, High-confidence estimation of small s-t reliabilities in directed acyclic networks, Networks 57 (2011), 376–388.
Citing Literature
