Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418284 | Discrete Applied Mathematics | 2014 | 15 Pages |
Abstract
In this paper we introduce the average reliability of a graph GG, avgRel(G), which is average value of the all terminal reliability of a graph GG on [0,1][0,1]. We show that while the determination of the average reliability of a graph is apparently intractable, it can be efficiently bounded. We show that the closure of the average reliabilities is the interval [0,1][0,1]. Finally, while in general there do not exist uniformly optimal graphs with respect to reliability, we apply average reliability to propose “good” graphs for network reliability, and provide evidence that a specific family of cyclic graphs are indeed good.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
J.I. Brown, D. Cox, R. Ehrenborg,