Network Reliability

Michael O. Ball, College of Business & Management, University of Maryland

Charles J. Colbourn, Department of Combinatorics and Optimization, University of Waterloo

J. Scott Provan, Department of Operations Research, University of North Carolina

Abstract

An extensive survey is given of binary and multistate reliability, including connectedness reliability and performability measures such as throughput, signal delay, and PERT project completion times. Research outlined includes: computational complexity, heuristics, efficient algorithms for special cases, problem reduction, bounds and approximations, and Monte Carlo techniques. A section is devoted to the use of these techniques in practice. Nearly 400 references are cited.