Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности
Автор: Мигов Денис Александрович
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая информатика
Статья в выпуске: 2 (6), 2010 года.
Бесплатный доступ
Предлагается способ получения формул для расчета вероятности связности подмножества вершин в графе с абсолютно надежными вершинами и ненадежными ребрами, основанный на переборе вариан- тов полного отсечения каждой из вершин. Формулы, полученные для быстрого расчета вероятности связности подмножества вершин в 4- и 5-вершинных графах, могут быть использованы при расчете такой вероятности для графов большой размерности методом ветвления.
Случайный граф, надежность сети, метод ветвления
Короткий адрес: https://sciup.org/14320020
IDR: 14320020
Список литературы Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности
- Colbourn Ch. J. The combinatorics of network reliability. N. Y.: Oxford Univ. Press, 1987. 160 p.
- Page L. B., Perry J. E. A practical implementation of the factoring theorem for network reliability//IEEE Trans. Reliability. 1988. V. 37, N 3. P. 259-267.
- Resende L. I. Implementation of a factoring algorithm for reliability evaluation of undirected networks//IEEE Trans. Reliability. 1988. V. 37, N 5. P. 462-468.
- Wood R. K. Triconnected decomposition for computing K-terminal network reliability//Networks. 1989. V. 19. P. 203-220.
- Shooman A. M., Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction//IEEE Proc. of the reliability and maintainability symp., Las Vegas (USA), 1992. P. 441-448.
- Carlier J., Lucet C. A decomposition algorithm for network reliability evaluation//Discrete Аppl. Мath. 1996. V. 65, N 1-3. P. 141-156.
- Родионов А. С., Родионова О. К. Некоторые методы ускорения расчета надежности информационных сетей//Тр. 30-й Междунар. конф. "Информационные технологии в науке, образовании, телекоммуникации и бизнесе" (IT+SF'2000), Гурзуф, Украина, 2003. Запорожье: Изд-во Запорож. гос. ун-та, 2003. С. 215-217.
- Rodionova O. K., Rodionov A. S., Choo H. Network probabilistic connectivity: Exact calculation with use of chains//Springer Lecture Notes Comput. Sci. 2004. V. 3046. P. 315-324.
- Rodionov A. S., Choo H. On generating random network structures: connected graphs//Springer Lecture Notes Comput. Sci. 2004. V. 3090. P. 483-491.
Статья научная
