Online topological ordering
Irit Katriel, Hans L. Bodlaender · ACM Transactions on Algorithms · 2006
It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O (min{ m 3/2 log n , m 3/2 + n 2 log n }) time, an improvement over the best known result of O ( mn ). In addition, we analyze the complexity of the same algorithm with respect to the treewidth k of the underlying undirected graph. We show that the algorithm runs in time O ( mk log 2 n ) for general k and that it can be implemented to run in O ( n log n ) time on trees, which is optimal. The algorithm also detects cycles in the input.