Liu, Hsiao-FeiHsiao-FeiLiuKUN-MAO CHAO2009-04-292018-07-052009-04-292018-07-05200703043975https://www.scopus.com/inward/record.uri?eid=2-s2.0-36049045045&doi=10.1016%2fj.tcs.2007.08.009&partnerID=40&md5=78970ac37257ce6951f564ce0430fd48Katriel 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.application/pdf520838 bytesapplication/pdfen-USAlgorithms; Online algorithms; Tight analysis; Topological orderjournal article10.1016/j.tcs.2007.08.0092-s2.0-36049045045http://ntur.lib.ntu.edu.tw/bitstream/246246/154557/1/16.pdf