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


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


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

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

Для k-терминальной надежности параллельно-последовательных графов существует два алгоритма с линейным временем работы. Сатайанарайана и Вуд [A.Satyanarayana and R.K.Wood “A linear time algorithm for computing k-terminal reliability in serial-parallel networks”, SIAM, J. Computing 14 (1985), 818-832] использовали последовательную, параллельную и двухступенчатую редукцию совместно с редукциями двухсвязных сетей, называемых также преобразованиями многогранник-цепочка, чтобы свести последовательно-параллельную терминальную сеть к одновершинному графу.

Когда две субсети сопряжены с s узлами, надежность их объединения может быть полностью определена из значений для каждой субсети. Это может быть фактически выполнено посредством алгоритма динамического программирования, чье время работы линейно по отношению к числу вершин, но экспоненциально относительно числа точек соединения. Метод Уолда и Кольбурна использует тот факт, что последовательно-параллельные графы могут быть рекурсивно разъединены с помощью парных разрезов в вершинах - то есть, последовательно параллельные графы имеют ширину дерева равную двум.


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