Name
Abstract | ||
|---|---|---|
The reliability polynomial of a graph counts its connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph’s reliability polynomial. We develop an improved SIS algorithm for estimating the reliability polynomial. The new algorithm runs in expected time (log (,)) at worst and ≈ in practice, compared to ( ) for the previous algorithm. We analyze the error bounds of this algorithm, including comparison to alternative estimation algorithms. In addition to the theoretical analysis, we discuss methods for estimating the variance and describe experimental results on a variety of random graphs. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-012-9703-x | Algorithmica |
Keywords | Field | DocType |
Reliability polynomial,Graph,Fully-polynomial relative approximation scheme,fpras,Network reliability,Sequential importance sampling,On-line algorithm,Incremental algorithm | Discrete mathematics,Graph,Importance sampling,Random graph,Polynomial,Reliability (computer networking),Mathematics | Journal |
Volume | Issue | ISSN |
68 | 4 | 0178-4617 |
Citations | PageRank | References |
3 | 0.50 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David G. Harris | 1 | 101 | 20.82 |
| Francis Sullivan | 2 | 49 | 17.33 |
| Beichl, Isabel | 3 | 63 | 22.58 |