複数の点集合の最大共通部分集合の近似可能性について
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,複数の点集合が与えられた時,各点集合の部分集合となるような点集合で点数が最大のもの(最大共通部分点集合)を求める問題について考察を行なう.なお,各点集合は回転および平行移動により適当な位置にずらすことが許されるものとする.主な結果として,点集合の個数に制約が無いときに1次元以上の任意の次元のユークリッド空間において,最大共通部分点集合を近似することが最大クリークの近似と少なくとも同程度以上に困難であることを示す.なお,この結果は頂点が座標値を持つグラフに対しても拡張できる.
- 一般社団法人情報処理学会の論文
- 1993-05-28
著者
関連論文
- 最小キーおよび最適部分構造スクリーンの近似
- 二つの点集合の最大共通部分点集合を求めるランダマイズド・アルゴリズム
- 二次元配列間の距離について
- タンパク質立体構造の折れ線による近似とその構造マッチングへの応用
- 可変長ギャップ付き文字列に対する近似マッチング・アルゴリズム
- タンパク質立体構造に対する部分構造検索およびアラインメント・アルゴリズム
- 高次元点集合の合同性判定について
- Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
- 複数の点集合の最大共通部分集合の近似可能性について