Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Burago D., Rougemont M. de

Fundamenta Informaticae

1998

Vol. 36, nr 4

307-315

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.