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


Группирование ребер - часть 4


Выделяются два потенциальных метода улучшения стратегии группирования ребер. Первый - заключается в рассмотрении более надежных субграфов для группировки; второй - связан c расширением рассматриваемых наборов проходов и разрезов с целью разрешения некоторых пересечений ребер (таким образом, теряя независимость наборов ребер в группировке). Мы рассматриваем второе расширение, которое используется более активно в следующем подразделе. Для первого метода оказалось выполнено мало работы. Используя эффективный точный алгоритм для достижимости в случае бесцикловых ориентированных графов, Раманатхан и Кольбурн [A.Ramanathan, and C.J.Colbourn, “Bounds on all-terminal reliability via arc packing”, Ars Combinatoria 23A, (1987), 91-94] получили улучшения верхних границ достижимости, а также всетерминальных верхних границ надежности. Однако использование группирования ребер с привлечение не минимальных проходов или набора разрезов не развивается, частично из-за нехватки точных алгоритмов для ограниченных классов, частично по причине трудности нахождения подходящей группы ребер.




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



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