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 / 2 log n, m3 / 2 + n2 log n}) 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 + m n1 / 2 log n)11In this paper, we assume that m = Ω (n). In fact, our analysis can be easily extended to prove that the algorithm runs in time Θ (min {m3 / 2 + m n1 / 2 log n, m3 / 2 log m + n}) without the assumption m = Ω (n).. © 2007 Elsevier Ltd. All rights reserved.