Sixty Years of Network Reliability

Agarwal, P.K., et al.: The resilience of WDM networks to probabilistic geographical failures. IEEE/ACM Trans. Netw. 21(5), 1525–1538 (2013)

Amin, A.T., Siegrist, K.T., Slater, P.J.: On the nonexistence of uniformly optimal graphs for pair-connected reliability. Networks 21(3), 359–368 (1991)

Amin, A.T., Siegrist, K.T., Slater, P.J.: On uniformly optimally reliable graphs for pairconnected reliability with vertex failures. Networks 23(3), 185–193 (1993)

Anderson, I.: Combinatorics of Finite Sets. Dover Books on Mathematics. Dover, New York (1987). ISBN: 9780486422572

Ball, M.O., Scott Provan, J.: Bounds on the reliability polynomial for shellable independence systems. SIAM J. Algebr. Discrete Methods 3(2), 166–181 (1982)

Ball, M.O., Scott Provan, J.: Calculating bounds on reachability and connectedness in stochastic networks. Networks 13(2), 253–278 (1983)

Barrera, J., Cancela, H., Moreno, E.: Topological optimization of reliable networks under dependent failures. Oper. Res. Lett. 43(2), 132–136 (2015)

Boesch, F.T.: On the synthesis of optimally reliable networks having unreliable nodes but reliable edges. In: INFOCOM ’88. Networks: Evolution or Revolution, Proceedings of the Seventh Annual Joint Conference of the IEEE Computer and Communcations Societies, pp. 829–834. IEEE (1988)

Brecht, T.B., Colbourn, C.J.: Lower bounds on two-terminal network reliability. Discrete Appl. Math. 21(3), 185–198 (1988)

Brown, J., Mol, L.: On the roots of the node reliability polynomial. Networks 68(3), 238–246 (2016)

Brown, J.I., Cox, D., Ehrenborg, R.: The average reliability of a graph. Discrete Appl. Math. 177, 19–33 (2014)

Brown, J.I., Li, X.: Uniformly optimal digraphs for strongly connected reliability. Networks 49(2), 145–151 (2007)

Bulka, D., Dugan, J.B.: A lower bound on the reliability of an n-dimensional hypercube. In: Proceedings Ninth Symposium on Reliable Distributed Systems, pp. 44–53 (1990)

Bulka, D., Dugan, J.B.: Network s–t reliability bounds using a 2-dimensional reliability polynomial. IEEE Trans. Reliab. 43(1), 39–45 (1994)

Burgos, J.M.: Factorization of network reliability with perfect nodes II: connectivity matrix. Discrete Appl. Math. 198, 91–100 (2016)

Burgos, J.M., Amoza, F.R.: Factorization of network reliability with perfect nodes I: introduction and statements. Discrete Appl. Math. 198, 82–90 (2016)

Canale, E., et al.: Diameter constrained reliability: complexity, distinguished topologies and asymptotic behavior. Networks 66(4), 296–305 (2015)

Canale, E., et al.: Full complexity analysis of the diameter-constrained reliability. Int. Trans. Oper. Res. 22(5), 811–821 (2015)

Cancela, H., et al.: Diameter constrained reliability of ladders and Spanish fans. Yugosl. J. Oper. Res. 26(1), 17–32 (2016)

Chen, Y., He, Z.: Bounds on the reliability of distributed systems with unreliable nodes and links. IEEE Trans. Reliab. 53(2), 205–215 (2004)

Colbourn, C.J.: Edge-packing of graphs and network reliability. Discrete Math. 72(1), 49–61 (1988)

Colbourn, C.J.: Network resilience. SIAM J. Algebr. Discrete Methods 8(3), 404–409 (1987)

Colbourn, C.J.: The Combinatorics of Network Reliability. Oxford University Press, New York (1987). ISBN 0-19-504920-9

Colbourn, C.J., Harms, D.D., Myrvold, W.J.: Reliability polynomials can cross twice. J. Frankl. Inst. 330(3), 629–633 (1993)

de Abreu, N.M.M.: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423(1), 53–73 (2007)

Doty, L.L.: Extremal connectivity and vulnerability in graphs. Networks 19(1), 73–78 (1989)

Dugas, M.R., Samaniego, F.J.: On optimal system designs in reliability-economics frameworks. Nav. Res. Logist. 54(5), 568–582 (2007)

El-Amawy, A., Latifi, S.: Properties and performance of folded hypercubes. IEEE Trans. Parallel Distrib. Syst. 2(1), 31–42 (1991)

Ellens, W., et al.: Effective graph resistance. Linear Algebra Appl. 435(10), 2491–2506 (2011)

Elspas, B.: Topological constraints on interconnection-limited logic. In: 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 133–137 (1964)

Evans, T., Smith, D.: Optimally reliable graphs for both edge and vertex failures. Networks 16(2), 199–204 (1986)

Frank, O., Gaul, W.: On reliability in stochastic graphs. Networks 12(2), 119–126 (1982)

Gertsbakh, I., Shpungin, Y., Vaisman, R.: Ternary Networks: Reliability and Monte Carlo. Springer, Berlin (2014). ISBN 3319064398

Gertsbakh, I.B., Shpungin, Y.: Models of Network Reliability: Analysis, Combinatorics, and Monte Carlo, 1st edn. CRC Press, Boca Raton (2009). ISBN: 1439817413

Gertsbakh, I.B., Shpungin, Y.: Network Reliability and Resilience. Springer, Berlin (2011). ISBN 978-3-642-22373-0

Goldschmidt, O., Jaillet, P., Lasota, R.: On reliability of graphs with node failures. Networks 24(4), 251–259 (1994)

Gross, D.J., Saccoman, J.T., Suffel, C.L.: Spanning Tree Results for Graphs and Multigraphs: A Matrix-Theoretic Approach. World Scientific, Singapore (2014). ISBN: 9789814566056

Gunawan, I.: Fundamentals of Reliability Engineering: Applications in Multistage Interconnection Networks. Wiley, New York (2014). ISBN: 978-1-118-54956-8

Guo, L., Guo, X.: Fault tolerance of hypercubes and folded hypercubes. J. Supercomput. 68(3), 1235–1240 (2014)

Harms, D.D., et al.: Network Reliability. Experiments with a Symbolic Algebra Environment. CRC Press, Boca Raton (1995). ISBN: 0-8493-3980-4

Hu, X.D., Hwang, F.K.: Reliabilities of chordal rings. Networks 22(5), 487–501 (1992)

Hu, X.D., Hwang, F.K.: Survival reliabilities of double loop networks. In: Global Telecommunications Conference, 1990, and Exhibition. ‘Communications: Connecting the Future’ (GLOBECOM’90), vol.2, pp. 674–677. IEEE (1990)

Hu, X.D., Hwang, F.K., Li, W.-C.I.W.: Most reliable double loop networks in survival reliability. Networks 23(5), 451–458 (1993)

Hwang, F.K., Wright, P.E.: Survival reliability of some double-loop networks and chordal rings. IEEE Trans. Comput. 44(12), 1468–1471 (1995)

Hwang, F.K.: A survey on multi-loop networks. Theoret. Comput. Sci. 299(1), 107–121 (2003)

Hwang, F.K., Li, W.-C.W.: Reliabilities of double-loop networks. Probab. Eng. Inf. Sci. 5(3), 255272 (1991)

Hwang, F.K., Wright, P.E., Hu, X.D.: Exact reliabilities of most reliable double-loop networks. Networks 30(2), 81–90 (1997)

Jukna, S.: Extremal Combinatorics: With Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2001). ISBN 9783540663133

Karp, R.M., Luby, M.: Monte-Carlo algorithms for the planar multiterminal network reliability problem. J. Complex. 1(1), 45–64 (1985)

Katerinis, P.: Toughness of graphs and the existence of factors. Discrete Math. 80(1), 81–92 (1990)

Kelmans, A.: Connectivity of probabilistic networks. Autom. Remote Control 29, 444–460 (1967)

Kelmans, A.: Some problems of network reliability analysis. Autom. Remote Control 26, 564–573 (1965)

Kirchhoff, G.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Ann. Phys. 148, 497–508 (1847)

Kuo, S.Y., Yeh, F.M., Lin, H.Y.: Efficient and exact reliability evaluation for networks with imperfect vertices. IEEE Trans. Reliab. 56(2), 288–300 (2007)

Liu, S., Cheng, K.-H., Liu, X.: Network reliability with node failures. Networks 35(2), 109–117 (2000)

Long, X., Tipper, D., Gomes, T.: Measuring the survivability of networks to geographic correlated failures. In: Optical Switching and Networking 14, Part 2 (2014). Special Issue on RNDM, pp. 117–133 (2013)

McAssey, M.P., Samaniego, F.J.: On uniformly optimal networks: a reversal of fortune? Commun. Stat. Theory Methods 43(10–12), 2452–2467 (2014)

Mohamed, M.H.S., et al.: An efficient evaluation for the reliability upper bound of distributed systems with unreliable nodes and edges. Int. J. Eng. Technol. 2(2), 107–110 (2010)

Monakhova, E.A.: A survey on undirected circulant graphs. In: Discrete Mathematics, Algorithms and Applications 04.01 (2012), p. 1250002

Moore, E.F., Shannon, C.E.: Reliable circuits using less reliable relays. J. Frankl. Inst. 262(3), 191–208 (1956)

Myrvold, W.: Reliable network synthesis: some recent developments. In: Proceedings of International Conference on Graph Theory, Combinatorics, Algorithms, and Applications. vol. 2, pp. 651–660 (1999)

Page, L.B., Perry, J.E.: A practical implementation of the factoring theorem for network reliability. IEEE Trans. Reliab. 37(3), 259–267 (1988)

Petingi, L., Rodriguez, J.: Reliability of networks with delay constraints. Congr. Numer. 152, 117–123 (2001)

Peyrat, C.: Diameter vulnerability of graphs. Discrete Appl. Math. 9(3), 245–250 (1984)

Politof, T., Satyanarayana, A.: A linear-time algorithm to compute the reliability of planar cube-free networks. IEEE Trans. Reliab. 39(5), 557–563 (1990)

Politof, T., Satyanarayana, A.: Efficient algorithms for reliability analysis of planar networks—a survey. IEEE Trans. Reliab. 35(3), 252–259 (1986)

Provan, S.J.: The complexity of reliability computations in planar and acyclic graphs. SIAM J. Comput. 15(3), 694–702 (1986)

Rodriguez-Velazquez, J.A., Kamisalic, A., Domingo-Ferrer, J.: On reliability indices of communication networks. Comput. Math. Appl. 58(7), 1433–1440 (2009)

Samaniego, F.J.: System Signatures and their Applications in Engineering Reliability. International Series on Operations Research and Management Science. Springer, Berlin (2007). ISBN: 978-0-387-71797-5

Satyanarayana, A., Chang, M.K.: Network reliability and the factoring theorem. Networks 13(1), 107–120 (1983)

Satyanarayana, A., Tindell, R.: Efficient Algorithms for the Evaluation of Planar Network Reliability. Tech. rep. DTIC Document (1993). http://oai.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA263602

Satyanarayana, A., KevinWood, R.: A linear-time algorithm for computing K-terminal reliability in series-parallel networks. SIAM J. Comput. 14(4), 818–832 (1985)

Shier, D.R.: Network Reliability and Algebraic Structures. Oxford University Press, Oxford (1991)

Shpungin, Y.: Networks with unreliable nodes and edges: Monte Carlo lifetime estimation. Int. J. Electr. Comput. Energ. Electron. Commun. Eng. 1(3):458–463. (2007). ISSN: 2010-376X

Smith, D.H.: Optimally reliable graphs for both vertex and edge failures. Comb. Probab. Comput. 2(1), 93100 (1993)

Smith, D.H.: Optimally reliable networks. Ann. Oper. Res. 33(2), 107–112 (1991)

Smith, D.H., Doty, L.L.: On the construction of optimally reliable graphs. Networks 20(6), 723–729 (1990)

Soh, S., Rai, S., Trahan, J.L.: Improved lower bounds on the reliability of hypercube architectures. IEEE Trans. Parallel Distrib. Syst. 5(4), 364–378 (1994)

Theologou, O.R., Carlier, J.G.: Factoring and reductions for networks with imperfect vertices. IEEE Trans. Reliab. 40(2), 210–217 (1991)

Tripathy, C.R., Mahapatra, R.N., Misra, R.B.: Reliability analysis of hypercube multicomputers. Microelectron. Reliab. 37(6), 885–891 (1997)

Van Slyke, R.M., Frank, H.: Network reliability analysis: part I. Networks 1, 279–290 (1971)

Vertigan, D.: The computational complexity of tutte invariants for planar graphs. SIAM J. Comput. 35(3), 690–712 (2005)

Wood, R.K.: Factoring algorithms for computing k-terminal network reliability. IEEE Trans. Reliab. 35(3), 269–278 (1986)

Yu, S., Shao, F.-M., Meng, H.: Uniformly optimal graphs in some classes of graphs with node failures. Discrete Math. 310(1), 159–166 (2010)

Zhou, Q., et al.: Network Robustness under Large-Scale Attacks. Springer, Berlin (2013). ISBN: 978- 1-4614-4859-4

Zhu, Q., et al.: On reliability of the folded hypercubes. Inf. Sci. 177(8), 1782–1788 (2007)