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

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

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

Спасибо заранее.

Raghava.

Ответы

Ответ 1

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

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

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

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

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

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

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

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

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

Ответ 2

Руководство по разработке алгоритмов содержит некоторую полезную информацию. Ключевые моменты:

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