平面に埋め込まれた木の最大類似部分を求めるアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,根があり順序がある2つの木,及び平面に埋め込まれた2つの木T_a,T_bについて,T_aと類似している部分をT_b内で探す問題を論じている.木の最大類似部分を表すため,木の間の極大C写像及びそれに基づくT_bの中の"T_aとの最大類似部分"を定義し,その最大類似部分の1つを抽出するアルゴリズムを述べている.このアルゴリズムの時間計算量と空間計算量は,根があり順序がある木では,それぞれΟ_T(N_aN_b)とΟ_S(N_aN_b)であり,平面に埋め込まれた木では,それぞれΟ_T(m_am_bN_aN_b)とΟ_S((m_a+m_b)N_a+N_b)である.ここで,N_a(N_b)とm_a(m_b)は,それぞれT_a(T_b)の頂点数と最大の頂点次数を表す.
- 社団法人電子情報通信学会の論文
- 1994-11-18
著者
関連論文
- 3次元グラフ構造の最大共通部分を求めるアルゴリズム
- 点パターンマッチングアルゴリズムの効率化
- 順序がない木の間の類似度問題
- 平面に埋め込まれた木の最大共通類似部分問題
- 順序がない木の最大類似部分問題
- 外平面グラフの点部分同型判定アルゴリズム
- 順序がない木の距離を求めるアルゴリズム
- 木の最大類似部分問題とそのアルゴリズム
- 二つの外平面描写の最大共通部分の抽出について
- 木の描写アルゴリズムの効率化
- 二つの木の最大共通部分グラフを求めるアルゴリズム
- 線図形の類似度とその計算法
- 根がなく巡回的順序がある木の間の距離とその計算法
- 木の距離の並列計算法
- ハッシュ法を用いた類似キー検索ファイル (メディア統合および環境統合のための高機能データベースシステム、および一般)
- 一般化LR法に基づく文脈自由言語の誤り訂正アルゴリズム
- 根がなく順序がない木の距離とその計算法
- 大型データベースのための最長共通部分列の一高速抽出法
- 大型データペースのための最長共通部分列の一高速抽出法
- D-1-2 グラフ描画アルゴリズムに基づいたデフォルメ路線図作成法(D-1. コンピュテーション, 情報・システム1)
- 根付き非順序木の最小幅描写問題の計算複雑度
- 木構造図の描写アルゴリズムの効率化
- BD木を用いたマルチレイヤデータ管理構造の改良
- 空間に埋め込まれた木のグラフ理論的距離とその計算法
- 空間に埋め込まれた木の距離とその計算法
- 構成文字ハッシュ法に基づく綴り誤りの高速訂正法
- 根がなく巡回的順序のある木の距離の逐次および並列計算法
- 類似データ検索のためのファイル構成法
- 線図形の類似度の計算法
- B木に基づく類名表記機能ファイルシステムの構成法
- 平面に埋め込まれた木の最大類似部分を求めるアルゴリズム
- 誤ったキーでも検索できるファイル構成法
- 平面グラフの最大重み窓問題
- あるグラフの極大頂点集合を表現するダイアグラム
- 階層的グラフの平面性判定アルゴリズム
- 2層配線における3端子ネットの分割
- 部品の端子間に配線を通過させない一層配線問題について
- 部品の反転を許さない一層平面配線問題について
- 引出し線を用いたラベル配置
- 引出し線を用いた地図ラベル配置アルゴリズム
- 引出し線を用いた地図ラベル配置アルゴリズム
- D-1-8 地図中の地点と線情報へのラベル配置のためのラベル候補作成法(D-1.コンピュテーション,一般講演)
- 地点の優先度を考慮した地図ラベル配置アルゴリズム
- グラフ描画へのラベル配置アルゴリズムの実験的評価
- グラフ描画へのラベル配置アルゴリズムの実験的評価
- D-1-1 優先度付き地図ラベル配置問題に対するラベル候補作成法(D-1. コンピュテーション, 情報・システム1)
- 辺がラベルをもつ無向グラフの描画法(グラフとネットワーク)
- D-1-2 辺がラベルをもつグラフの描画アルゴリズム
- グラフ描画における辺のラベルの配置法
- グラフ描画における辺のラベルの配置法
- D-1-10 引出し線を用いたラベル配置アルゴリズムの改良(D-1.コンピュテーション,一般講演)
- クラス編成問題に対する平等な割当決定法
- D-1-11 図形データの重なり判定を高速化するデータ構造の提案(D-1.コンピュテーション,一般講演)
- D-1-9 二次元点パターンマッチング問題に対する高速なアルゴリズム(D-1.コンピュテーション,一般講演)
- TLAESAに基づく近似κ近傍検索手法(研究速報)
- 最大重みクリークを効率良く抽出するための頂点系列の生成法
- D-4-9 類似検索手法TLAESAの改良(D-4. データ工学, 情報・システム1)
- D-4-8 地理データに対する領域管理手法の実験的評価(D-4. データ工学, 情報・システム1)
- D-1-3 頂点がグループ分けされた階層的グラフの描画法(D-1. コンピュテーション, 情報・システム1)
- Comparability supergraphを用いた最大重みクリーク問題の厳密解法
- Chordal SupergraphとChordal Subgraphによる最大クリーク問題の緩和問題構成法について
- A-34 グラフ最適化問題に対する緩和問題の構成法の提案(最適化,A.アルゴリズム・基礎)
- D-1-3 グラフの最大独立頂点集合数の上界の計算法の提案
- グラフ描画における頂点ラベルの配置法
- 類似検索手法による無向グラフの最短経路探索法
- ゲーム理論を用いたパケット網経路制御法
- 根付き非順序木の同型判定アルゴリズム
- GBD木における線分の分割法の改良
- GBD木における線分の分割法の改良
- 2種類の理想距離によるEadesのグラフ描画法の改良
- グラフ描画における頂点ラベルの配置法
- 容量制限付きk-center問題の近似解法の実験的評価