Algebraic Methods Applied to Network Reliability Problems

An algebraic structure underlying network reliability problems is presented for determining the 2-terminal reliability of directed networks. An iterative algorithm is derived from this algebraic perspective to solve the $(s,j)$-terminal reliability problem simultaneously for all nodes j. In addition to providing an exact answer (in the form of a reliability polynomial), the algorithm also yields a nondecreasing sequence of approximate solutions guaranteed to be lower bounds on the exact solution. Empirical results, presented for two different implementations of the algorithm, show that useful approximate solutions can be obtained in a reasonable amount of computation time.