Item

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\{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. If the input contains cycles, the algorithm detects this.