Abstract
We introduce classes of narrow graphs (including grid strips of fixed width), for which the graph reliability problem admits a polynomial time algorithm. Using this algorithm, we show that graph reliability is computable in polynomial time for the average complexity with respect to a Gaussian distribution. The latter is defined as follows: the vertices are numbered by integers {1,2, . . . n}, and the probability that an edge between i and j is present is e-|i-j|2.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 307-315 |
| Number of pages | 9 |
| Journal | Fundamenta Informaticae |
| Volume | 36 |
| Issue number | 4 |
| DOIs | |
| State | Published - Dec 1998 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Algebra and Number Theory
- Information Systems
- Computational Theory and Mathematics
Fingerprint
Dive into the research topics of 'On the Average-Case Complexity of the Graph Reliability Problem on Gaussian Distributions'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver