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

DOI10.1137/S0036144501387141zbMath0972.05045MaRDI QIDQ2753004

David R. Karger

Publication date: 23 October 2001

Published in: SIAM Review (Search for Journal in Brave)

zbMATH Keywords

minimum cut; approximation scheme; network reliability

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

90B25: Reliability, availability, maintenance, inspection in operations research

05C85: Graph algorithms (graph-theoretic aspects)

68M15: Reliability, testing and fault tolerance of networks and computer systems

05C40: Connectivity

Related Items

Inapproximability of the Tutte polynomial, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width