4551
правка
Отрицательные циклы во взвешенных орграфах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Отрицательные циклы во взвешенных орграфах (посмотреть исходный код)
Версия от 13:33, 17 января 2016
, 17 января 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
Для планарных орграфов получены лучшие границы. Для случая, когда стоимости ребер являются целыми числами, в [9] предложен алгоритм с временем исполнения <math>O(n^{4/3} \; log (nL))</math>. В случае ребер с вещественными значениями стоимости алгоритм с временем исполнения <math>O(n log^3 \; n)</math> можно найти в работе [5]. | Для планарных орграфов получены лучшие границы. Для случая, когда стоимости ребер являются целыми числами, в [9] предложен алгоритм с временем исполнения <math>O(n^{4/3} \; log (nL))</math>. В случае ребер с вещественными значениями стоимости алгоритм с временем исполнения <math>O(n \; log^3 \; n)</math> можно найти в работе [5]. | ||