二つの点集合の最大共通部分点集合を求めるランダマイズド・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
二つの点集合が与えられた時、各点集合の部分集合と合同で要素数最大の点集合を求める問題は、種々のパターンマッチング問題と関連するので重要である。二次元の場合において単純なアルゴリズムではO(n^5logn)時間かかるが、本稿ではランダマイズド・アルゴリズムを用いることによりO(n^4polylog(n))時間で計算できることを示す。この結果は組合せ幾何の結果を利用することにより更に改善することが可能である。なお、このアルゴリズムは高次元に拡張することも可能であり、また、ここで使用した技法はタンパク質立体構造の近似アラインメントにも応用可能である。
- 1995-07-20
著者
関連論文
- 最小キーおよび最適部分構造スクリーンの近似
- 二つの点集合の最大共通部分点集合を求めるランダマイズド・アルゴリズム
- 二次元配列間の距離について
- タンパク質立体構造の折れ線による近似とその構造マッチングへの応用
- 可変長ギャップ付き文字列に対する近似マッチング・アルゴリズム
- タンパク質立体構造に対する部分構造検索およびアラインメント・アルゴリズム
- 高次元点集合の合同性判定について
- Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
- 複数の点集合の最大共通部分集合の近似可能性について