On the average-case complexity of the graph reliability problem on Gaussian distributions

• Autorzy: Burago D. , Rougemont M. de
• Języki publikacji: EN

Abstrakty

EN

We introduce classes of narrow graphs (including grid strips of fixed width), for which the graph reliabiblity 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 Gausian distribution. The latter is defined as follows: the vertices are numbered by integers {1,2,...n}, and probability that an edge between i and j is present is e-|i-j|2.

Słowa kluczowe

EN

graph reliability; average complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1998
• Tom: Vol. 36, nr 4
• Strony: 307--315
• Opis fizyczny: bibliogr. 6 poz.

Twórcy

autor

Burago D.

autor

Rougemont M. de

• Department of mathematics, Penn-State University, University Park, USA,