A tight analysis of the Katriel–Bodlaender algorithm for online topological ordering

Katriel and Bodlaender [Irit Katriel, Hans L. Bodlaender, Online topological ordering, ACM Transactions on Algorithms 2 (3) (2006) 364–379] modify the algorithm proposed by Alpern et al. [Bowen Alpern, Roger Hoover, Barry K. Rosen, Peter F. Sweeney, F. Kenneth Zadeck, Incremental evaluation of computational circuits, in: Proceedings of the First Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), 1990, pp. 32–42] for maintaining the topological order of the n nodes of a directed acyclic graph while inserting m edges and prove that their algorithm runs in O(min{m3/2logn,m3/2+n2logn}) time and has an Ω(m3/2) lower bound. In this paper, we give a tight analysis of their algorithm by showing that it runs in time Θ(m3/2+mn1/2logn)1.