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{m(3/2) log n, m(3/2) + n(2) log n}) time and has an ohm(m(3/2))) lower bound. In this paper, we give a tight analysis of their algorithm by showing that it runs in time theta(m(3/2) + mn(1/2) log n)(1). (c) 2007 Elsevier B.V. All rights reserved.
tight analysis algorithms topological order online algorithms