Reliabilities of consecutive-2 graphs.

A consecutive-2 graph is a graph where each vertex is associated with a failure probability and the graph is considered failed if any two adjacent vertices both fail. Recently, the problem of computing reliability for general graph is shown to be #P- complete while polynomial algorithms exist for trees. In this paper we give a linear time algorithm for a class of graphs including forests and cycles.