Примеры сетевых топологий


Методы, базирующиеся на маршрутах и разрезах - часть 5


Методы, основанные на доминантности, гарантируют, что будут просматриваться только релевантные состояния и, таким образом, достигается улучшение в отношении почти всех других методов включения-исключения. Методы, базирующиеся на факторизации (для неориентированного случая), также генерируют только релевантные состояния. Подход Сатайанарайана-Чанга реализует наилучшее возможное время вычисления, используя последовательные и параллельные сокращения. Фактически, во всетерминальном случае, так как число деревьев связи превышает доминантность, алгоритм улучшает все методы, основанные на минипроходах. Наконец, методы, основанные на независимых произведениях, хотя и сопряжены с трудностями анализа, дают два важных алгоритма: алгоритм Болла-Немхаузера для вычисления всетерминальной надежности за полиномиальное время при заданном числе минипроходов, и алгоритм Прована-Болла, который вычисляет двухтерминальную надежность за полиномиальное время при заданном числе миниразрезов.

Этот полезный механизм измерения сложности в терминах числа минипроходов, миниразрезов или релевантных состояний позволяет видеть, что отобранные методы в действительности лучше остальных алгоритмов оценки сетевой надежности.




Начало  Назад  Вперед



Книжный магазин