Online Topological Ordering

Abstract

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{m3/2 log n,m3/2 + n2 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 log2 n) for general k and that it can be implemented to run in O(n log n) time on trees, which is optimal. If the input contains cycles, the algorithm detects this.