Affiliations: Department of Mathematics, Penn-State University, University Park, U.S.A. email address : burago@math.psu.edu | Department of Computer Science, University Paris II, Paris, France. email address : mdr@lri.fr
Note: [] Address for correspondence: Department of Mathematics, Penn-State University, University Park, USA.
Note: [] Department of Computer Science, University Paris II, Paris, France.
Abstract: We introduce classes of narrow graphs (including grid strips of fixed width), for which the graph reliability problem admits a polynomial time algorithm. Using this algorithm, we show that graph reliability is computable in polynomial time for the average complexity with respect to a Gaussian distribution. The latter is defined as follows: the vertices are numbered by integers {1,2, ...n}, and the probability that an edge between i and j is present is e−|i−j|2.
