Journal
DISCRETE OPTIMIZATION
Volume 6, Issue 4, Pages 436-445Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.disopt.2009.05.003
Keywords
All-terminal reliability; Graph; Chip firing; Multicomplex; M-partitionable; M-shelling; Bounds
Ask authors/readers for more resources
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. (C) 2009 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available