最小キーおよび最適部分構造スクリーンの近似
スポンサーリンク
概要
- 論文の詳細を見る
化学構造データベースでは検索の効率化のために部分構造スクリーンが用いられるが、本稿ではスクリーンとして使用される最適な部分構造を選択する問題について考察する。この問題は関係データベース理論における最小キー問題と密接に関連しているが、両者ともにNP困難であるので、多項式時間近似アルゴリズムの観点から議論を行う。本稿では、両者ともに近似度はSET COVER問題と同等(θ(log n))であること、Kolmogorov計算量を応用することにより部分構造スクリーン問題が平均的には定数以内の近似が可能であること、などを示す。
- 一般社団法人情報処理学会の論文
- 1995-09-21
著者
関連論文
- プライバシー保護した相関ルールマイニングに関する再考
- プライバシー保護した相関ルールマイニングに関する再考
- プライバシー保護した相関ルールマイニングに関する再考
- チャンネルネットワークにおける安全なメッセージ分配
- ビザンチン故障のあるスターグラフ上のブロードキャスティング
- 故障のあるスターネットワーク上の最適なブロードキャスティング(並列・分散)
- 故障のあるスターネットワーク上の最適なブロードキャスティング(並列・分散)
- ローテータグラフにおけるノンアダプティブな耐故障ファイル転送
- プライバシー保護した分散的ドキュメントクラスタリング
- プライバシー保護した分散的ドキュメントクラスタリング
- 積グラフの独立な全域木(計算モデルと計算の複雑さに関する研究)
- ハイパーキューブ、メッシュ、トーラス上のブロードキャストの耐故障性
- 積グラフの独立全域木について
- オンライン全域木の平均コンペティティブ比について
- 改良有限オートマトン公開鍵暗号システムの解析
- 最小キーおよび最適部分構造スクリーンの近似
- 直積ネットワークにおける高信頼性ブロードキャスト
- ランダム故障に対する2進ジャンピング回路網上での情報散布の耐故障性について
- 二つの点集合の最大共通部分点集合を求めるランダマイズド・アルゴリズム
- 二次元配列間の距離について
- タンパク質立体構造の折れ線による近似とその構造マッチングへの応用
- 可変長ギャップ付き文字列に対する近似マッチング・アルゴリズム
- タンパク質立体構造に対する部分構造検索およびアラインメント・アルゴリズム
- 高次元点集合の合同性判定について
- Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
- 複数の点集合の最大共通部分集合の近似可能性について