Мигов Д.А.
Расчёт вероятности связности случайного графа с применением сечений
Рассматривается задача точного расчёта вероятности связности случайного графа. Данная характеристика является одним из основных показателей надёжности сетей. Для решения предлагается подход основанный на структурной декомпозиции сети. Ускорение достигается за счёт сведения расчёта надёжности исходной сети к расчёту надёжности группы сетей меньшей размерности. Разработан метод, позволяющий учитывать сразу группу двухвершинных сечений, что существенно быстрее чем рекурсивный обход сечений с использованием соответствующей формулы. Проведено экспериментальное исследование целесообразности проведения декомпозиции для сечений размера более чем два.
Работа поддержана проектом РФФИ № 18-07-00460
К списку докладов