順序がない木の最大類似部分問題

• Item type: SIG Technical Reports(1)
• 公開日: 1995-11-17
• タイトル: 順序がない木の最大類似部分問題
• タイトル / 言語: en
• タイトル: Largest Similar Substructure Problems for Unordered Trees (Extended Abstract)
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 神戸大学自然科学研究科
• 著者所属: 神戸大学工学部
• 著者所属(英): en
• 著者所属(英): The Graduate School of Science and Technology, Kobe University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Kobe University
• 著者名: 劉紹明; 田中, 栄一
• 著者名(英): Shaoming, Liu; Eiichi, Tanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 根があり順序がない木をR?木と言い，根がなく順序がない木を単に”木”と言う．本論文では，二つのR?木T_a，T_b，あるいは二つの木T_a，T_bについて，T_aと類似している部分をT_b内で探す問題を論じ，T_aと類似しているT_bの最大部分の1つを抽出するアルゴリズムを述べている．アルゴリズムの時間計算量と空間計算量は，R?木の場合も木の場合も，それぞれO_T(^3N_aN)とO_S(N_aN)である．ここで，N_a(_)はT_a(_)の頂点数を表し，mはT_aとT_bの最大の頂点次数を表す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper discusses the problems of largest similar substructures (in short, LSS) in rooted and unordered trees (in short, R-trees) and those in unrooted and unordered trees (in short, trees). For two R-trees (or trees) T_a and T_b, LSS in T_b to T_a is defined, and two algorithms for finding one of the LSSs for R-trees and that for trees are proposed. The time and space complexities of both algorithms are O_T(m^3N_aN_b) and O_S(mN_aN_b), respectively, where m is the largest degree of a vertex of T_a and T_b, and N_a(N_b) is the number of vertices of T_a(T_b).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 109(1995-AL-048), p. 23-30, 発行日 1995-11-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会