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

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