Chip firing and all-terminal network reliability bounds |
| |
Authors: | Jason I Brown Charles J Colbourn Richard J Nowakowski |
| |
Institution: | aMathematics and Statistics, Dalhousie University, Halifax, NS, Canada B3H 3J5;bComputer Science and Engineering, Arizona State University, PO Box 878809, Tempe, AZ 85287-8809, USA |
| |
Abstract: | The (all-terminal) reliability of a graph G is the probability that all vertices are in the same connected component, given that vertices are always operational but edges fail independently each with probability p. Computing reliability is #P-complete, and hence is expected to be intractable. Consequently techniques for efficiently (and effectively) bounding reliability have been the major thrust of research in the area. We utilize a deep connection between reliability and chip firings on graphs to improve previous bounds for reliability. |
| |
Keywords: | All-terminal reliability Graph Chip firing Multicomplex M-partitionable M-shelling Bounds |
本文献已被 ScienceDirect 等数据库收录! |
|