4551
правка
Отрицательные циклы во взвешенных орграфах: различия между версиями
Материал из WEGA
Отрицательные циклы во взвешенных орграфах (посмотреть исходный код)
Версия от 23:50, 17 января 2016
, 17 января 2016→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Таким образом, представляет интерес сокращение разрыва между двумя указанными значениями временной сложности – даже для специальных классов графов или случая с целочисленными стоимостями ребер. | Таким образом, представляет интерес сокращение разрыва между двумя указанными значениями временной сложности – даже для специальных классов графов или случая с целочисленными стоимостями ребер. | ||
Единственный случай, когда обе временные сложности совпадают, касается орграфов с малой древесной шириной [3]; в результате этот класс графов в настоящий момент является классом самого общего вида. Для планарных орграфов результат, приведенный в [3], только на полилогарифмический коэффициент отличается от алгоритма с временем исполнения O(n), вычисляющего дерево кратчайших путей в случае неотрицательной стоимости ребер. | Единственный случай, когда обе временные сложности совпадают, касается орграфов с малой древесной шириной [3]; в результате этот класс графов в настоящий момент является классом самого общего вида. Для планарных орграфов результат, приведенный в [3], только на полилогарифмический коэффициент отличается от алгоритма с временем исполнения O(n), вычисляющего дерево кратчайших путей в случае неотрицательной стоимости ребер. | ||
