A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

Heng Guo, Mark Jerrum

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publication45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
EditorsIoannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald Sannella
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages68:1-68:12
Number of pages12
Volume107
ISBN (Print)978-3-95977-076-7
DOIs
Publication statusPublished - 9 Jul 2018
Event45th International Colloquium on Automata, Languages, and Programming - Prague, Czech Republic
Duration: 9 Jul 201813 Jul 2018
https://iuuk.mff.cuni.cz/~icalp2018/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume107
ISSN (Electronic)1868-8969

Conference

Conference45th International Colloquium on Automata, Languages, and Programming
Abbreviated titleICALP 2018
CountryCzech Republic
CityPrague
Period9/07/1813/07/18
Internet address

Keywords

  • Approximate counting
  • Network Reliability
  • Sampling
  • Markov chains

Fingerprint Dive into the research topics of 'A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability'. Together they form a unique fingerprint.

Cite this