{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:42:12Z","timestamp":1787341332737,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N004221\/1"],"award-info":[{"award-number":["EP\/N004221\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that in an undirected graph, assuming each edge fails independently, the remainder of the graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak [ Random Structures Algorithms, 44 (2014), pp. 201--223] that the expected running time of the \u201ccluster-popping\u201d algorithm in bidirected graphs is bounded by a polynomial in the size of the input.<\/jats:p>","DOI":"10.1137\/18m1201846","type":"journal-article","created":{"date-parts":[[2019,5,9]],"date-time":"2019-05-09T11:32:58Z","timestamp":1557401578000},"page":"964-978","source":"Crossref","is-referenced-by-count":21,"title":["A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability"],"prefix":"10.1137","volume":"48","author":[{"given":"Heng","family":"Guo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,5,9]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2018.188.2.1"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100206"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335422"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130210"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.37236\/1627"},{"key":"atypb6","unstructured":"C. J. Colbourn,\n                      The Combinatorics of Network Reliability\n                      , Oxford University Press, 1987."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.04.003"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/12088330X"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20460"},{"key":"atypb10","unstructured":"H. Guo and M. Jerrum,\n                      A polynomial-time approximation algorithm for all-terminal network reliability\n                      , in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), I. Chatzigiannakis et al., eds., LIPIcs. Leibniz Int. Proc. Inform. 107, Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2018, 68."},{"key":"atypb11","first-page":"342","author":"Guo H.","year":"2017","journal-title":"ACM"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210507"},{"key":"atypb13","first-page":"259","author":"Harris D. G.","year":"2014","journal-title":"SIAM"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-011-0777-6"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"atypb16","unstructured":"M. Jerrum,\n                      On the Complexity of Evaluating Multivariate Polynomials\n                      , Ph.D. dissertation, Tech. report CST-11-81, Department of Computer Science, University of Edinburgh, 1981."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298340"},{"key":"atypb20","first-page":"635","author":"Karger D. R.","year":"2016","journal-title":"IEEE"},{"key":"atypb21","first-page":"755","author":"Karger D. R.","year":"2017","journal-title":"IEEE"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(85)90021-4"},{"key":"atypb23","first-page":"235","author":"Kolipaka K. B. R.","year":"2011","journal-title":"ACM"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2013.07.001"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"atypb26","unstructured":"J. G. Oxley,\n                      Matroid Theory\n                      , Oxford University Press, 1992."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579368"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000195"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"D. J. A. Welsh,\n                      Complexity: Knots, Colourings and Counting\n                      , London Math. Soc. Lecture Note Ser. 186, Cambridge University Press, 1993.","DOI":"10.1017\/CBO9780511752506"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<210::AID-RSA2>3.0.CO;2-R"},{"key":"atypb33","first-page":"296","author":"Wilson D. B.","year":"1996","journal-title":"ACM"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1201846","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:14:08Z","timestamp":1787339648000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1201846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1201846"],"URL":"https:\/\/doi.org\/10.1137\/18m1201846","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}