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

Question

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

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

Answer 1

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

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

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

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

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

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

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

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

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

Answer 2

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

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