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

Транзитивное замыкание графа определяется e. г. здесь: http://mathworld.wolfram.com/TransitiveClosure.html

Это легко возможно в O (n ^ 3), где n - количество вершин. Мне было интересно, можно ли это сделать за время O (n ^ 2).

7 голосов | спросил nes1983 1 AMpWed, 01 Apr 2009 03:58:37 +040058Wednesday 2009, 03:58:37

3 ответа


0

Неа. Я не думаю, что есть алгоритм O (n 2 ) для этого. Я ожидал бы, что если бы существовал такой алгоритм, вы могли бы решить проблему всех пар кратчайших путей в O (n 2 ), что не так. Асимптотически быстрый алгоритм, который я могу придумать, - это реализация алгоритма Дейкстры по кратчайшему пути с кучей Фибоначчи (O ( n 2 log n ) в не очень плотные графики).

ответил Mehrdad Afshari 1 AMpWed, 01 Apr 2009 04:02:10 +040002Wednesday 2009, 04:02:10
0

Хм. Я нашел алгоритм, который вычисляет транзитивное замыкание за время ожидания O (n ^ 2).

ответил nes1983 1 AMpWed, 01 Apr 2009 04:08:49 +040008Wednesday 2009, 04:08:49
0

Учитывая, что это:

  

Можете ли вы придумать O (kn ^ 2 + m) транзитивное замыкание /уменьшение   алгоритм, где k - количество пропущенных /лишних ребер в переходном   закрытие /уменьшение?

Все еще считается открытым вопросом для людей, которые думают о таких вещах больше, чем мы, я бы сказал: «Я не знаю».

(Но если вы решите это и захотите получить докторскую степень, я знаю этот алгоритм.)

ответил MarkusQ 1 AMpWed, 01 Apr 2009 04:09:22 +040009Wednesday 2009, 04:09:22

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132