2026-07-21T14:57:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9072 2024-03-06T10:43:18Z ddc:004 open_access

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability Guo, Heng Jerrum, Mark Approximate counting Network Reliability Sampling Markov chains 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 a undirected graph, assuming each edge fails independently, the remaining graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Heng Guo and Mark Jerrum 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.68 urn:nbn:de:0030-drops-90727 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.68 eng https://creativecommons.org/licenses/by/3.0/legalcode