A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem

1998/09/09 by David R. Karger, Karger, David R. · 3 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Reliability and Maintenance Optimization #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/9809012

To appear in SICOMP

arxiv created 1998/09/09 · openalex publication_date 1998/09/09 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability.

Cited by

• On the complex zeros and the computational complexity of approximating the reliability polynomial
• Estimating the Size of Union of Sets in Streaming Models
• Hedgegraph Polymatroids

Related

• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Exact solutions for the two- and all-terminal reliabilities of a simple ladder network
• An FPRAS for two terminal reliability in directed acyclic graphs
• Node Reliability: Approximation, Upper Bounds, and Applications to Network Robustness
• Assessing the reliability polynomial based on percolation theory