4551
правка
Отрицательные циклы во взвешенных орграфах: различия между версиями
Материал из WEGA
Отрицательные циклы во взвешенных орграфах (посмотреть исходный код)
Версия от 23:45, 17 января 2016
, 17 января 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
Для случая орграфов с малой древесной шириной (и вещественными значениями стоимости ребер) в [3] предложен оптимальный алгоритм с временем исполнения O(n). Неформально древесная ширина t графа G представляет собой параметр, измеряющий, насколько структура G близка к структуре дерева. К примеру, класс графов с малой древесной шириной включает серийно-параллельные графы (t = 2) и внешнепланарные графы (t = 2). Оптимальный параллельный алгоритм решения той же задачи на базе модели вычислений CREW PRAM был предложен в [2]. | Для случая орграфов с малой древесной шириной (и вещественными значениями стоимости ребер) в [3] предложен оптимальный алгоритм с временем исполнения O(n). Неформально древесная ширина t графа G представляет собой параметр, измеряющий, насколько структура G близка к структуре дерева. К примеру, класс графов с малой древесной шириной включает [[серийно-параллельный граф|серийно-параллельные графы]] (t = 2) и [[внешнепланарный граф|внешнепланарные графы]] (t = 2). Оптимальный параллельный алгоритм решения той же задачи на базе модели вычислений CREW PRAM был предложен в [2]. | ||
== Применение == | == Применение == | ||
