Fast sequential importance sampling to estimate the graph reliability polynomial

DOI10.1007/S00453-012-9703-XMaRDI QIDQ476443zbMATH OpenOpenAlexFDO

Authors 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

sequential importance samplingonline algorithmreliability polynomialFPRASincremental algorithmnetwork reliabilityfully-polynomial relative approximation scheme

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Sequential importance sampling algorithms for estimating the all-terminal reliability polynomial of sparse graphs
• scientific article; zbMATH DE number 4083346
• An approximation algorithm for the coefficients of the reliability polynomial
• Computing network reliability coefficients
• scientific article; zbMATH DE number 1263176

Cites work

• scientific article; zbMATH DE number 4083346 (Why is no real title available?)
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• scientific article; zbMATH DE number 1263176 (Why is no real title available?)
• A Monte Carlo Sampling Plan for Estimating Network Reliability
• An approximation algorithm for the coefficients of the reliability polynomial
• Collective dynamics of `small-world' networks
• Counting almost minimum cutsets with reliability applications
• Countingk-component forests of a graph
• Efficiency of a Good But Not Linear Set Union Algorithm
• Fully Dynamic Algorithms for 2-Edge Connectivity
• Lower bounds for the condition number of Vandermonde matrices
• Maintenance of 2- and 3-Edge-Connected Components of Graphs II
• Sparse reliable graph backbones
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Two Algorithms for Unranking Arborescences

Cited in

(9)

• Computing network reliability coefficients
• Sequential importance sampling algorithms for estimating the all-terminal reliability polynomial of sparse graphs
• A Sequential Importance Sampling Algorithm for Counting Linear Extensions
• scientific article; zbMATH DE number 4083346 (Why is no real title available?)
• Sequential importance sampling for estimating expectations over the space of perfect matchings
• Stochastic enumeration with importance sampling
• Estimating the Number of s-t Paths in a Graph
• Speeding up computation of the reliability polynomial coefficients for a random graph
• An approximation algorithm for the coefficients of the reliability polynomial

This page was built for publication: Fast sequential importance sampling to estimate the graph reliability polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476443)