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


Эффективные алгоритмы для ограниченных классов - часть 2


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

Получение эффективных алгоритмов путем ограничения ширины дерева рассматривается в литературе для большинства эффективных алгоритмов. Важно заметить, что у планарных графов ширина дерева зависит от числа вершин, несмотря на то, что ширина дерева ограничена O (

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

Помимо графов с фиксированной шириной, мало что известно по поводу мер надежности неориентированных графов. Гильберт разработал элегантный рекурсивный метод вычисления всетерминальной надежности полных сетей, когда все ребра работоспособны с равной вероятностью. Метод требует линейного времени. Он обобщается естественным образом для k-терминальной надежности, и для полных двучастных систем, а также связанных сетей. Метод существенно зависит от соблюдения условия, что несколько неизоморфных субграфов связаны множественно с некоторым числом вершин. Методу динамического программирования нужно тогда только определить полиномиальное число субсетей.

При обращении к мерам надежности ориентированных графов выделяется один важный алгоритм. Болл и Прован разработали алгоритм с линейным временем для вычисления достижимости в ориентированных нециклических сетях. Алгоритм базируется на соблюдении условия, что такая сеть функционирует (с точки зрения достижимости) тогда и только тогда, когда каждый некорневой узел имеет, по крайней мере, одну из входных дуг в рабочем состоянии.

В последнее время проводятся интенсивные исследования эффективно решаемых классов проблем узловой надежности. Узловая двухтерминальная надежность (без отказов ребер) допускает эффективные алгоритмы для графов перестановок и графов интервалов. Из этого можно получить эффективные алгоритмы для двухтерминальной надежности при отказе ребра, когда сеть имеет линейный граф, который является графом интервалов или перестановок, используя переход от проблем отказов ребер, к проблемам отказов узлов.

Классы, для которых известны точные эффективные алгоритмы, достаточно редки и не относятся к числу наиболее практичных. Несмотря на это, присутствие точных алгоритмов даже для редких классов может использоваться для ускорения точных алгоритмов для более широких классов, которые упрощают сеть некоторым образом; они имеют также использование для вычисления ограничений надежности.




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



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