Fast computation of bounds for two-terminal network reliability

Journal Article (Journal Article)

In this paper, an algorithm for the fast computation of network reliability bounds is proposed. The evaluation of the network reliability is an intractable problem for very large networks, and hence approximate solutions based on reliability bounds have assumed importance. The proposed bounds computation algorithm is based on an efficient BDD representation of the reliability graph model and a novel search technique to find important minpaths/mincuts to quickly reduce the gap between the reliability upper and lower bounds. Furthermore, our algorithm allows the control of the gap between the two bounds by controlling the overall execution time. Therefore, a trade-off between prediction accuracy and computational resources can be easily made in our approach. The numerical results are presented for large real example reliability graphs to show the efficacy of our approach. © 2014 Elsevier B.V. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Sebastio, S; Trivedi, KS; Wang, D; Yin, X

Published Date

  • November 1, 2014

Published In

Volume / Issue

  • 238 / 3

Start / End Page

  • 810 - 823

International Standard Serial Number (ISSN)

  • 0377-2217

Digital Object Identifier (DOI)

  • 10.1016/j.ejor.2014.04.035

Citation Source

  • Scopus