Fast sequential importance sampling to estimate the graph reliability polynomial

DOI10.1007/s00453-012-9703-xzbMath1303.05192OpenAlexW1981755798MaRDI 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 algorithmnetwork reliabilitysequential importance samplingreliability polynomialFPRASincremental algorithmfully-polynomial relative approximation scheme

Mathematics Subject Classification ID

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

Related Items (3)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

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