Fast sequential importance sampling to estimate the graph reliability polynomial
DOI10.1007/S00453-012-9703-XzbMATH Open1303.05192OpenAlexW1981755798MaRDI QIDQ476443FDOQ476443
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
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
sequential importance samplingonline algorithmreliability polynomialFPRASincremental algorithmnetwork reliabilityfully-polynomial relative approximation scheme
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)
Cites Work
- Title not available (Why is that?)
- Collective dynamics of `small-world' networks
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Efficiency of a Good But Not Linear Set Union Algorithm
- A Monte Carlo Sampling Plan for Estimating Network Reliability
- Two Algorithms for Unranking Arborescences
- Lower bounds for the condition number of Vandermonde matrices
- Title not available (Why is that?)
- An approximation algorithm for the coefficients of the reliability polynomial
- Sparse reliable graph backbones
- Counting almost minimum cutsets with reliability applications
- Title not available (Why is that?)
- Countingk-component forests of a graph
- Fully Dynamic Algorithms for 2-Edge Connectivity
- Maintenance of 2- and 3-Edge-Connected Components of Graphs II
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
- Sequential importance sampling for estimating expectations over the space of perfect matchings
- Title not available (Why is that?)
- Estimating the Number of s-t Paths in a Graph
- Stochastic enumeration with importance sampling
- 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)
