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

Для разреженных орграфов общего вида в [8] был предложен алгоритм для решения задачи нахождения отрицательного цикла за время <math>O(n + \tilde{ \gamma } ^{1.5} log \; \tilde{ \gamma } )</math>, где <math>\tilde{ \gamma } \;</math> – топологическая мера входного разреженного орграфа G, значение которой меняется от 1 до <math>\Theta (n) \;</math>. Неформально <math>\tilde{ \gamma } \;</math> представляет минимальное количество внешнепланарных подграфов, удовлетворяющих определенным свойствам отделимости и полученных в результате декомпозиции графа G. В частности, <math>\tilde{ \gamma } \;</math> пропорционально <math>\gamma (G) + q \;</math>, где G предполагается вложенным в ориентируемую поверхность рода <math>\gamma (G) \;</math> таким образом, чтобы минимизировать количество q граней, совместно покрывающих все вершины. Например, если граф G является внешнепланарным, то <math>\tilde{ \gamma } = 1 \;</math>, в результате для такого случая получаем оптимальный алгоритм с временем исполнения O(n). Алгоритм в [8] не требует необходимого наличия такого вложения входного графа. В той же статье показано, что случайные графы <math>G_{n,p} \;</math> с пороговой функцией 1/n являются планарными с вероятностью 1, а ожидаемое значение <math>\tilde{ \gamma } \;</math> для них равно O(1). Кроме того, в [8] предложено эффективное распараллеливание алгоритма на базе модели вычислений CREW PRAM.