推移的閉包を求めるアルゴリズムのならし計算量 (II)

• Item type: SIG Technical Reports(1)
• 公開日: 1989-06-23
• タイトル: 推移的閉包を求めるアルゴリズムのならし計算量 (II)
• タイトル / 言語: en
• タイトル: Amortized Complexity of a Transitive Closure Algorithm (II)
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学工学部
• 著者所属: KDD
• 著者所属: 名古屋大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engeneering, Nagoya University
• 著者所属(英): en
• 著者所属(英): KDD
• 著者所属(英): en
• 著者所属(英): Faculty of Engeneering, Nagoya University
• 著者名: 平田, 富夫; 島谷, 隆司; 稲垣, 康善
• 著者名(英): Tomio, Hirata; Takashi, Shimatani; Yasuyoshi, Inagaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフGに辺を挿入する、あるいは除去するという操作を施しながら、何らかの質問(query)に答えるダイナミックなデータ構造がいくつか提案されている．筆者らは、先に、有向グラフGに辺の挿入と除去を繰り返し行うときのGの推移的閉包をオンラインで求めるアルゴリズムを提案し、そのならし計算量を解析した．本論文では、このアルゴリズムの改良版を提案する．これにより、Gに閉路が生じる場合も取り扱えるようになった．改良されたアルゴリズムは、Gがn個の頂点を持つとき、m回の辺の挿入とd回の辺の除去をO((d+1)mn+(m-d)n)時間で実行する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a directed graph G, suppose that edges are added to or deleted from G, and we want to compute its transitive closure in the on-line manner. This paper presents an improved version of the previously proposed algorithm. The result of the paper is as follows: the on-line computation of the transitive closure of G with n nodes, while m eddges are added to and d eddges are deleted from G, can be done in O((d+1)mn+(m-d)n) time. The new algorithm works even if an cycle occures in G, which is forbidden in the original algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1989, 号 51(1989-AL-008), p. 1-6, 発行日 1989-06-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会