https://scholars.lib.ntu.edu.tw/handle/123456789/117599
標題: | A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering | 作者: | Liu, Hsiao-Fei KUN-MAO CHAO |
關鍵字: | Algorithms; Online algorithms; Tight analysis; Topological order | 公開日期: | 2007 | 卷: | 389 | 期: | 1-2 | 起(迄)頁: | 182-189 | 來源出版物: | Theoretical Computer Science | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-36049045045&doi=10.1016%2fj.tcs.2007.08.009&partnerID=40&md5=78970ac37257ce6951f564ce0430fd48 | ISSN: | 03043975 | DOI: | 10.1016/j.tcs.2007.08.009 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。