Отрицательные циклы во взвешенных орграфах: различия между версиями

Таким образом, представляет интерес сокращение разрыва между двумя указанными значениями временной сложности – даже для специальных классов графов или случая с целочисленными стоимостями ребер.

Единственный случай, когда обе временные сложности совпадают, касается орграфов с малой древесной шириной [3]; в результате этот класс графов в настоящий момент является классом самого общего вида. Для планарных орграфов результат, приведенный в [3], только на полилогарифмический коэффициент отличается от алгоритма с временем исполнения O(n), вычисляющего дерево кратчайших путей в случае неотрицательной стоимости ребер.