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

Question

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

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

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

12

algorithm graph closures

задан Micha Wiedenmann 14 August 2018 в 13:40

1 ответ

Другие вопросы по тегам:

algorithm graph closures

Похожие вопросы:

score 11 · Answer 1

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

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