Abstract
In this paper we introduce the average reliability of a graph G, avgRel(G), which is average value of the all terminal reliability of a graph G on [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]. 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.
| Original language | English |
|---|---|
| Pages (from-to) | 19-33 |
| Number of pages | 15 |
| Journal | Discrete Applied Mathematics |
| Volume | 177 |
| DOIs | |
| State | Published - Nov 20 2014 |
Bibliographical note
Funding Information:This research was partially supported by grant RGPIN 170450-2013 from Natural Sciences and Engineering Research Council of Canada and the National Science Foundation ( DMS 0902063 ).
Funding
This research was partially supported by grant RGPIN 170450-2013 from Natural Sciences and Engineering Research Council of Canada and the National Science Foundation ( DMS 0902063 ).
| Funders | Funder number |
|---|---|
| U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China | DMS 0902063 |
Keywords
- All terminal reliability
- Average reliability
- Closure
- Cycle bundles
- Optimal graph
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics