{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T09:21:04Z","timestamp":1760606464269},"reference-count":22,"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":7802,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1985,6]]},"abstract":"Abstract<\/jats:title>Let G<\/jats:italic> = (V,E<\/jats:italic>) be an undirected graph whose edges may fail, and let G<\/jats:italic>k<\/jats:sub> denote G<\/jats:italic> with a set k<\/jats:italic> \u2286 V<\/jats:italic> specified. Edge failures are assumed to be statistically independent and to have known probabilities. The k<\/jats:italic>\u2010terminal reliability of G<\/jats:italic>k<\/jats:sub>, denoted R<\/jats:italic>(G<\/jats:italic>k<\/jats:sub>), is the probability that all vertices in k<\/jats:italic> are connected by working edges. Computing k<\/jats:italic>\u2010terminal reliability is an NP\u2010hard problem not known to be in NP. A factoring algorithm for computing network reliability recursively applies the formula R<\/jats:italic>(G<\/jats:italic>k<\/jats:sub>) = P<\/jats:italic>i<\/jats:sub>R<\/jats:italic>(G<\/jats:italic>k\u2032<\/jats:sub>*e<\/jats:italic>i<\/jats:sub> + q<\/jats:italic>i<\/jats:sub>R<\/jats:italic>(G<\/jats:italic>k<\/jats:sub> \u2212 e<\/jats:italic>i<\/jats:sub>)), where G<\/jats:italic>k\u2032<\/jats:sub>*e<\/jats:italic>i<\/jats:sub> is G<\/jats:italic>k<\/jats:sub> with edge e<\/jats:italic>i<\/jats:sub> contracted, G<\/jats:italic>k<\/jats:sub> \u2212 e<\/jats:italic>i<\/jats:sub> is G<\/jats:italic>k<\/jats:sub> with e<\/jats:italic>i<\/jats:sub> deleted and p<\/jats:italic>i<\/jats:sub> = 1 \u2212 q<\/jats:italic>i<\/jats:sub> is the reliability of edge e<\/jats:italic>i<\/jats:sub>. Various reliability\u2010preserving reductions may be performed after each factoring operation in order to reduce computational complexity. The complexity of a slightly restricted factoring algorithm using standard reductions, along with newly developed polygon\u2010to\u2010chain reductions, will be bounded below by an invariant of G<\/jats:italic>, the \u201cminimum domination.\u201d For 2 \u2264 \u2223K\u2223 \u2264 5 or \u2223V\u2223 \u2212 2 \u2264 \u2223K\u2223 \u2264 \u2223V\u2223, this bound is always achievable. The factoring algorithm with polygon\u2010to\u2010chain reductions will always perform as well as or better than an algorithm using only standard reductions, and for some networks, it will outperform the simpler algorithm by an exponential factor. This generalizes early results that were only valid for K<\/jats:italic> = V<\/jats:italic>. Removing the restriction on edge selection leaves results essentially unchanged in the upper range of \u2223K<\/jats:italic>\u2223, but minimum domination becomes only a tight upper bound for the lower range.<\/jats:p>","DOI":"10.1002\/net.3230150204","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T19:21:23Z","timestamp":1178911283000},"page":"173-190","source":"Crossref","is-referenced-by-count":60,"title":["A factoring algorithm using polygon\u2010to\u2010chain reductions for computing K\u2010terminal network reliability"],"prefix":"10.1002","volume":"15","author":[{"given":"R. Kevin","family":"Wood","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100206"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_4_2","volume-title":"Statistical Theory of Reliability","author":"Barlow R. E.","year":"1975"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100404"},{"key":"e_1_2_1_6_2","volume-title":"A graph theoretic appraisal of the complexity of network reliability algorithms","author":"Chang M. K.","year":"1981"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1109\/TCT.1973.1083657","article-title":"A Boolean algebra method for computing the terminal reliability in a communication network","volume":"20","author":"Fratta L.","year":"1976","journal-title":"IEEE Trans. Circuit Theory"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1981.5221152"},{"key":"e_1_2_1_11_2","unstructured":"R.JohnsonSome combinatorial aspects of network reliability Ph. D. Thesis Dept. of IEOR University of California Berkeley (1982)."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(56)90559-2"},{"key":"e_1_2_1_13_2","first-page":"627","article-title":"The analysis of redundancy networks","volume":"39","author":"Moskowitz F.","year":"1958","journal-title":"AIEE Trans. (Commun. Electron)"},{"key":"e_1_2_1_14_2","unstructured":"A.RosenthalComputing reliability of complex systems Ph. D. Thesis University of California Berkeley (1974)."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132031"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1982.5221215"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130107"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1978.5220266"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"A.Satyanarayana andR. K.Wood Polygon\u2010to\u2010chain reductions and network reliability ORC 82\u20104 Operations Research Center University of California Berkeley (1982).","DOI":"10.21236\/ADA116276"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_21_2","volume-title":"Connectivity in Graphs","author":"Tutte W. T.","year":"1980"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"R. K.Wood Polygon\u2010to\u2010chain reductions and extensions for computingK\u2010terminal reliability in an undirected network ORC 81\u201012 Operations Research Center University of California. Berkeley (1982).","DOI":"10.21236\/ADA124145"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230150204","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230150204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T21:22:51Z","timestamp":1697836971000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230150204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,6]]}},"alternative-id":["10.1002\/net.3230150204"],"URL":"https:\/\/doi.org\/10.1002\/net.3230150204","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,6]]}}}