IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v32y1984i3p478-492.html
   My bibliography  Save this article

A Survey of Network Reliability and Domination Theory

Author

Listed:
  • Avinash Agrawal

    (Tymnet, Inc., San Jose, California)

  • Richard E. Barlow

    (University of California, Berkeley, California)

Abstract

We present a brief survey of the current state of the art in network reliability. We survey only exact methods and do not consider Monte Carlo methods. Most network reliability problems are, in the worst case, NP-hard and are, in a sense, more difficult than many standard combinatorial optimization problems. Nevertheless, there are, in fact, linear and polynomial time algorithms for network reliability problems of special structure. We review general methods for network reliability computation and discuss the central role played by domination theory in network reliability computational complexity. We also point out the connection with the more general problem of computing the reliability of coherent structures. The class of coherent structures contains both directed and undirected networks as well as logic (or fault) trees without not gates. This topic is a rich area for further research.

Suggested Citation

  • Avinash Agrawal & Richard E. Barlow, 1984. "A Survey of Network Reliability and Domination Theory," Operations Research, INFORMS, vol. 32(3), pages 478-492, June.
    • Handle: RePEc:inm:oropre:v:32:y:1984:i:3:p:478-492
    DOI: 10.1287/opre.32.3.478
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.32.3.478
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.32.3.478?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jorge Navarro & Rafael Rubio, 2010. "Comparisons of coherent systems using stochastic precedence," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 19(3), pages 469-486, November.
    2. Zarezadeh, S. & Asadi, M. & Balakrishnan, N., 2014. "Dynamic network reliability modeling under nonhomogeneous Poisson processes," European Journal of Operational Research, Elsevier, vol. 232(3), pages 561-571.
    3. Zhang, Chi & Ramirez-Marquez, José Emmanuel & Wang, Jianhui, 2015. "Critical infrastructure protection using secrecy – A discrete simultaneous game," European Journal of Operational Research, Elsevier, vol. 242(1), pages 212-221.
    4. Yi, He & Cui, Lirong & Balakrishnan, Narayanaswamy, 2021. "Computation of survival signatures for multi-state consecutive-k systems," Reliability Engineering and System Safety, Elsevier, vol. 208(C).
    5. Chi Zhang & Jose Ramirez-Marquez, 2013. "Protecting critical infrastructures against intentional attacks: a two-stage game with incomplete information," IISE Transactions, Taylor & Francis Journals, vol. 45(3), pages 244-258.
    6. Smeitink, E. & Dijk, N.M. van & Haverkort, B.R., 1990. "Product forms for availability," Serie Research Memoranda 0040, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    7. Ramirez-Marquez, Jose E. & Rocco, Claudio M. & Gebre, Bethel A. & Coit, David W. & Tortorella, Michael, 2006. "New insights on multi-state component criticality and importance," Reliability Engineering and System Safety, Elsevier, vol. 91(8), pages 894-904.
    8. Goharshady, Amir Kafshdar & Mohammadi, Fatemeh, 2020. "An efficient algorithm for computing network reliability in small treewidth," Reliability Engineering and System Safety, Elsevier, vol. 193(C).
    9. Borgonovo, E., 2010. "The reliability importance of components and prime implicants in coherent and non-coherent systems including total-order interactions," European Journal of Operational Research, Elsevier, vol. 204(3), pages 485-495, August.
    10. E. Borgonovo & C. L. Smith, 2011. "A Study of Interactions in the Risk Assessment of Complex Engineering Systems: An Application to Space PSA," Operations Research, INFORMS, vol. 59(6), pages 1461-1476, December.
    11. Jorge Navarro, 2016. "Stochastic comparisons of generalized mixtures and coherent systems," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(1), pages 150-169, March.
    12. Barker, Kash & Ramirez-Marquez, Jose Emmanuel & Rocco, Claudio M., 2013. "Resilience-based network component importance measures," Reliability Engineering and System Safety, Elsevier, vol. 117(C), pages 89-97.
    13. Navarro, Jorge & Rychlik, Tomasz, 2010. "Comparisons and bounds for expected lifetimes of reliability systems," European Journal of Operational Research, Elsevier, vol. 207(1), pages 309-317, November.
    14. Cancela, Héctor & Petingi, Louis, 2007. "Properties of a generalized source-to-all-terminal network reliability model with diameter constraints," Omega, Elsevier, vol. 35(6), pages 659-670, December.
    15. Jorge Navarro & Pedro Hernandez, 2008. "Mean residual life functions of finite mixtures, order statistics and coherent systems," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 67(3), pages 277-298, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:32:y:1984:i:3:p:478-492. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.