{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T02:05:34Z","timestamp":1768010734235,"version":"3.49.0"},"reference-count":20,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7254,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1986,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The probability that a computer network is operational in an environment of statistically independent link failures has been widely studied. Three natural problems arise, when all nodes are to be connected (all\u2010terminal reliability), when two nodes are to communicate (2\u2010terminal reliability), and when <jats:italic>k<\/jats:italic> specified nodes are to communicate (<jats:italic>k<\/jats:italic>\u2010terminal reliability); the latter case includes the first two. Each of these reliability measures is NP\u2010hard to compute, and thus efficiently computable reliability bounds are of significant interest. To date, the all\u2010terminal and 2\u2010terminal cases have been treated separately, and few results apply to the <jats:italic>k<\/jats:italic>\u2010terminal case. In this paper, we develop a simple strategy to obtain <jats:italic>k<\/jats:italic>\u2010terminal reliability bounds. In the process, we demonstrate improvements on the previous best bounds for all\u2010terminal, <jats:italic>k<\/jats:italic>\u2010terminal, and 2\u2010terminal reliability. Computational experience with these new bounds is reported, by comparing the new lower bounds to existing lower bounds.<\/jats:p>","DOI":"10.1002\/net.3230160404","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T21:21:05Z","timestamp":1178918465000},"page":"369-380","source":"Crossref","is-referenced-by-count":18,"title":["Improving reliability bounds in computer networks"],"prefix":"10.1002","volume":"16","author":[{"given":"Timothy B.","family":"Brecht","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles J.","family":"Colbourn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"J. Y.Assous Bounds on terminal reliability. Preprint (1985)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0603016"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"e_1_2_1_6_2","unstructured":"T. B.BrechtandC. J.Colbourn Lower bounds for two\u2010terminal network reliability. CCNG Report E\u2010127 University of Waterloo (1985)."},{"key":"e_1_2_1_7_2","unstructured":"E. H.CarrascoandC. J.Colbourn Reliability bounds for networks with statistical dependence. Proc. INFOCOM86 Miami (1986)290\u2013292."},{"key":"e_1_2_1_8_2","unstructured":"C. J.ColbournandD. D.Harms Bounding all\u2010terminal reliability in computer networks. CCNG Report E\u2010123 University of Waterloo 1985."},{"key":"e_1_2_1_9_2","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/2313491"},{"key":"e_1_2_1_11_2","unstructured":"I. M.Jacobs Connectivity in probabilistic graphs. Technical Report 356 ERL MIT 1959."},{"key":"e_1_2_1_12_2","first-page":"187","volume-title":"A theorem of finite sets. I. Theory of Graphs","author":"Katona G.","year":"1966"},{"key":"e_1_2_1_13_2","first-page":"444","article-title":"Connectivity of probabilistic networks","volume":"29","author":"Kel'mans A. K.","year":"1967","journal-title":"Automat. Remote Control"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1525\/9780520319875-014","volume-title":"The number of simplices in a complex. I. Mathematical Optimization Techniques","author":"Kruskal J. B.","year":"1963"},{"key":"e_1_2_1_15_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E.","year":"1976"},{"key":"e_1_2_1_16_2","first-page":"118","article-title":"Lower bound of network reliability","volume":"8","author":"Lomonosov M. V.","year":"1972","journal-title":"Prob. Inf. Trans."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(56)90559-2"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612335"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010307"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120408"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230160404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230160404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T10:33:32Z","timestamp":1697884412000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230160404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,12]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1986,12]]}},"alternative-id":["10.1002\/net.3230160404"],"URL":"https:\/\/doi.org\/10.1002\/net.3230160404","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,12]]}}}