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

В работе [6] удалось сократить требуемый объем с <math>O(n^3) \; </math> до <math>O(n^2) \;</math>. От множителя log n удалось избавиться [7, 10]. Другие компромиссы между временем обновления и временем запроса приводятся в [1, 7, 8, 9, 10]. Рандомизированный алгоритм транзитивного замыкания, включающий только операции удаления, с общим временем исполнения <math>O(mn) \; </math>, был предложен в [8]; здесь m – исходное число ребер в графе. Простой алгоритм Монте-Карло для транзитивного замыкания в ациклических графах приведен в [5]. Динамический алгоритм достижимости с единственным источником в диграфе представлен в [8, 9]. Алгоритм поиска кратчайших путей между всеми парами может обеспечить практически такое же время обновления [2].