{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T07:48:52Z","timestamp":1767858532936,"version":"3.49.0"},"reference-count":32,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8533,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this article, computational procedures are presented for generating bounds on measures of network reliability. The two measures considered, reachability and connectedness, are the probability that there is an operating path from a node to all other nodes in a directed (respectively undirected) stochastic network. Our bounds, which are given in terms of polynomials in <jats:italic>p<\/jats:italic>, the common arc failure probability, are based on recent bounding results developed by the authors for the class of shellable independence systems. Two pairs of bounds are given: weaker bounds whose computation time is bounded by a polynomial in the size of the network and tighter bounds whose computation time is bounded by a polynomial in the size of the network and the number of minimum\u2010cardinality network cuts. Computational results are also given which evaluate the quality of the bounds. The generation of the bounds involves several interesting path and cut counting problems.<\/jats:p>","DOI":"10.1002\/net.3230130210","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T15:18:15Z","timestamp":1178896695000},"page":"253-278","source":"Crossref","is-referenced-by-count":112,"title":["Calculating bounds on reachability and connectedness in stochastic networks"],"prefix":"10.1002","volume":"13","author":[{"given":"Michael O.","family":"Ball","sequence":"first","affiliation":[]},{"given":"J. Scott","family":"Provan","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A.","year":"1974"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.4.823"},{"key":"e_1_2_1_4_2","unstructured":"M. O.Ball Network reliability analysis: algorithms and complexity. Ph.D. Thesis Cornell University (1977)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100206"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0603016"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1002\/net.1975.5.3.253","article-title":"The minimum number of edges and vertices in a graph with edge connectivity N and MN\u2010Bonds","volume":"5","author":"Bixby R.","year":"1975","journal-title":"Networks"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100404"},{"key":"e_1_2_1_9_2","first-page":"91","volume-title":"Combinatorial Algorithms","author":"Edmonds J.","year":"1972"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_12_2","first-page":"255","article-title":"Computer communication network design\u2010Experience with theory and practice","volume":"40","author":"Frank H.","year":"1972","journal-title":"AFIPS Natl. Comput. Conf. Expo. Conf. Proc."},{"key":"e_1_2_1_13_2","first-page":"31","article-title":"Applications of an algorithm for networks","volume":"2","author":"Gardner M. L.","year":"1980","journal-title":"Congressus Numeratium"},{"key":"e_1_2_1_14_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90120-4"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"key":"e_1_2_1_17_2","unstructured":"G.Katona A theorem of finite sets. InTheory of Graphs (Proceedings of Tihany Colloquim Sept. 1966) P. Erdos and G. Katona Eds. (1966) pp.209\u2013214."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/andp.18471481202"},{"key":"e_1_2_1_18_3","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/TCT.1958.1086426","volume":"5","year":"1958","journal-title":"IRE Trans. Circuit Theory"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1525\/9780520319875-014"},{"key":"e_1_2_1_20_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0130017"},{"key":"e_1_2_1_22_2","first-page":"285","article-title":"The shortest path through a maze","volume":"30","author":"Moore E. F.","year":"1959","journal-title":"Ann. Computation Lab. Harvard Univ."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(56)90559-2"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120902"},{"key":"e_1_2_1_25_2","unstructured":"J. S.ProvanandM. O.Ball The complexity of counting cuts and computing the probability that a graph is connected. University of Maryland at College Park College of Business and Management Working Paper MS\/S #81\u2010002 (1981)."},{"key":"e_1_2_1_26_2","first-page":"133","volume-title":"Reliability and Fault Tree Analysis","author":"Rosenthal A.","year":"1975"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132031"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1978.5220266"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-1220-1_3"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002449X"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010307"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130210","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T09:16:13Z","timestamp":1697793373000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["10.1002\/net.3230130210"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130210","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}