Fast sequential importance sampling to estimate the graph reliability polynomial

DOI10.1007/s00453-012-9703-xzbMath1303.05192MaRDI QIDQ476443

J. Herrera, Sumit K. Garg

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9703-x

zbMATH Keywords

online algorithm; network reliability; sequential importance sampling; reliability polynomial; FPRAS; incremental algorithm; fully-polynomial relative approximation scheme

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C85: Graph algorithms (graph-theoretic aspects)

68W27: Online algorithms; streaming algorithms

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

A Sequential Importance Sampling Algorithm for Counting Linear Extensions, Sequential importance sampling for estimating expectations over the space of perfect matchings, Stochastic enumeration with importance sampling

Cites Work

• Lower bounds for the condition number of Vandermonde matrices
• A Monte Carlo Sampling Plan for Estimating Network Reliability
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Sparse Reliable Graph Backbones
• Counting almost minimum cutsets with reliability applications
• Countingk-component forests of a graph
• Fully Dynamic Algorithms for 2-Edge Connectivity
• Efficiency of a Good But Not Linear Set Union Algorithm
• Two Algorithms for Unranking Arborescences
• Maintenance of 2- and 3-Edge-Connected Components of Graphs II
• Collective dynamics of ‘small-world’ networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item