Транзитивное замыкание графа определяется е. г. здесь: http://mathworld.wolfram.com/TransitiveClosure.htmlАсимметричное время выполнения, необходимое для вычисления транзитивного замыкания графика?
Это легко возможно в O (n^3), где n - число вершин. Мне было интересно, можно ли это сделать за время O (n^2).
Nope. Я не думаю, что существует алгоритм O (n). Я бы ожидал, что если бы такой алгоритм существовал, вы могли бы решить все проблемы с краткими краями пары в O (n) тоже, что не так. Асимптотически быстрый алгоритм, о котором я могу думать, представляет собой реализацию алгоритма кратчайшего пути Дейкстры с кучей Фибоначчи (O (n log n) в не очень плотных графах).
Хм. Я нашел алгоритм, который вычисляет транзитивное замыкание в O (n^2) ОЖИДАЕМОЕ время выполнения.
Учитывая, что это:
Можете ли вы придумать O (кп^2 + т) транзитивного замыкания/восстановления алгоритма, где к количество недостающих/дополнительных ребер в транзитивной закрытия/уменьшение?
Все еще считается открытым вопросом людей, которые думают об этих вещах больше, чем мы, я бы сказал: «Я не знаю».
(Но если вы решить и хотите доктора философии, я знаю, что алгоритм.)
с каким случайным распределением? – jpalecek
нет идеи. я не хочу использовать его, потому что я не хочу рандомизации в окружающем меня алгоритме. он находится здесь: http://www.springerlink.com/content/f511w61n62l17168/ – nes1983