A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Submitting institution
-
University of Edinburgh
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 126549936
- Type
- D - Journal article
- DOI
-
10.1137/18M1201846
- Title of journal
- SIAM Journal on Computing
- Article number
- -
- First page
- 964
- Volume
- 48
- Issue
- 3
- ISSN
- 0097-5397
- Open access status
- Compliant
- Month of publication
- May
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
C - Foundations of Computation
- Citation count
- 4
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Network reliability is the probability of a stochastic network being connected. This quantity is an important topic studied extensively both in operation research and in combinatorics. Exact evaluation of this quantity is computationally hard, and this paper gives the first efficient approximation algorithm. This resolves a long-standing open problem since the 80s and complements a famous algorithm by Karger (1999) which approximates network unreliability. Subsequently, it has inspired a number of other approximation algorithms. The conference version has won the best paper award in ICALP 2018. The full version is published in the prestigious journal SIAM J. Comput.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -