наиболее известный транзитивный алгоритм закрытия для графика

Question

С точки зрения времени выполнения, какой самый известный транзитивный алгоритм закрытия для ориентированных графов?

В настоящее время я использую алгоритм Варшалла, но его O (n^3). Хотя из-за графического представления моя реализация немного улучшается (вместо проверки всех ребер он проверяет все исходящие края). Существует ли какой-либо транзитивный алгоритм закрытия, который лучше этого? В частности, есть ли что-то специально для многопоточных архитектур разделяемой памяти?

Заранее спасибо.

Raghava.

Answer 1

Algorithm Design manual содержит полезную информацию. Ключевые моменты:

• Переходное замыкание так же сложно, как и матричное умножение; поэтому самая известная граница - это Coppersmith–Winograd algorithm, которая работает в O (n^2.376), но на практике, вероятно, не стоит использовать алгоритмы умножения матрицы.
• Для эвристического ускорения сначала вычислите сильно связанные компоненты.

Answer 2

В данной статье обсуждается эффективность различных алгоритмов транзитивного замыкания:

http://www.vldb.org/conf/1988/P382.PDF

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

Существует также эта страница Эско Nuutila, в котором перечислено несколько последних алгоритмы:

http://www.cs.hut.fi/~enu/tc.html

Его докторская диссертация, опубликованная на этой странице, может быть лучшим местом для начала:

http://www.cs.hut.fi/~enu/thesis.html

С этой страницы:

Эксперименты также показывают, что с интервальным представлением и новыми алгоритмами транзитивное замыкание может быть вычислено , как правило, во времени, линейном по размеру входного графика.