点集合の距離重複度列のノルムと最大部分集合問題
スポンサーリンク
概要
- 論文の詳細を見る
ユークリッド平面内の二つの点集合P,Qに対して、各々の部分集合で、互いに合同なものを共通部分集合という。この論文では点数最大の共通部分集合を計算する問題(LCP)を考察する。そのために、距離重複度ベクトルの内積の概念を導入し、その解析を行なう。さらに、高次元の場合に、この内積の概念を拡張する。内積の値に対する上界を用いて、LCPの高速解法を設計する事が出来る。この講演原稿では、ページ制限の都合で4次元以上の場合の結果の解説は省く。
- 一般社団法人情報処理学会の論文
- 1997-01-23
著者
-
阿久津 達也
東京大学 医科学研究所 ヒトゲノム解析センター
-
徳山 豪
日本アイ・ビー・エム東京基礎研究所
-
徳山 豪
日本アイ・ビー・エム
-
阿久 津達也
東京大学医科学研究所ヒトゲノム解析センター
-
玉木 久夫
日本アイ・ビー・エム東京基礎研究所
-
玉木 久夫
明治大学理工学部情報科学科
-
玉木 久夫
日本アイ・ビー・エム 東京基礎研
-
Tamaki Hisao
The School Of Science And Technology Meiji University
-
Tamaki Hisao
Department Of Computer Science Meiji University
-
Hisao Tamaki
Department Of Computer Science Meiji University.
関連論文
- 画像切り出しに対するアルゴリズムの提案 (アルゴリズムと計算機科学の数理的基盤とその応用)
- センサーネットワークの位相情報の検知に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 基本図形分割可能領域の最適切り出しアルゴリズム
- 非交差最小木の計算複雑度のパラメタ依存について
- Wireless Ad-Hocネットワークにおける干渉軽減法に関する研究
- 都市距離空間への新規高速道路の最適建設問題に対する擬凸最適化を用いた改良アルゴリズム
- ヨーロピアンアジアンオプションの効率的な価格付けの手法 : AMOアルゴリズムの実装と解析の改良
- 進化木のQuarted distanceの計算アルゴリズムの実装
- 多変数パラメトリック探索による最小値最大最適化問題の解法
- 分子生物情報学の現状と動向 (「分子生物情報学の新展開」)
- 特集「分子生物情報学の新展開の編集にあたって (「分子生物情報学の新展開」)
- 最適ハイウェイ配置問題
- 2.高密度部分グラフの抽出 : その計算限界と打破(特定領域研究「新世代の計算限界-その解明と打破-」)
- 地形図からの最適ピラミッドの構成アルゴリズム
- 多値属性を用いた最適なデータセグメンテーションを生成するアルゴリズム
- 幾何学アルゴリズムとその応用
- ランダムアルゴリズムの話題から
- 割り当て問題に対するランダムアルゴリズムの実験的検証
- 点集合の距離重複度列のノルムと最大部分集合問題
- 密な部分グラフ問題の貪欲解法
- 放物線のアレンジメントの組合せ複雑度について
- 割り当て問題に対するランダマイズド・アルゴリズムの実験的検証
- 線分族と三角形族の中での直交探索
- Kリンク最短パス問題と行列探索
- 三角形族の中での直交探索
- 単体内の点集合の分割について(LP新解法)
- Geometric Problems on Ad-Hoc Network Design (Computational Geometry and Discrete Mathematics)
- D-022 動画に対するコメントを利用した自動Web検索システム(データベース,一般論文)
- A-003 アドホックネットワーク上でのランダム局所近傍を利用した幾何ルーティングアルゴリズムの設計と解析(モデル・アルゴリズム・プログラミング,一般論文)
- RA-006 リストページ自動分割問題の最適グラフ分割を用いた解法の提案と評価(モデル・アルゴリズム・プログラミング,査読付き論文)
- アドホックネットワーク上でのランダム局所近傍を利用した幾何ルーティングアルゴリズムの設計と解析
- メッシュネットワークにおけるジオメトリックルーティングに関する研究
- 数学的整合性を持つデジタル直線集合
- ディジタル星型領域とその応用
- D_036 Webデータの自動抽出とデータ変換(D分野:データベース)
- 関数近似における幾何学アルゴリズムの最近の進展 : データ解析への応用に向けて(新世代の計算限界-その解明と打破-招待解説論文)
- Web検索結果におけるクラスタリングアルゴリズムの研究
- アメリカン・アジアンオプションの価格の近似に対する計算幾何手法的アプローチ
- アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム(計算機科学の理論とその応用)
- ヨーロピアン・アジアンオプションの価格付けに関する近似的解法
- ディスクレパンシー基準によるディジタルハーフトーニング : 自動評価手法と最適化手法
- 実数列の大域的丸めの数え上げ
- DNAマイクロアレイ画像の解析
- 特別講演:デジタル平面の計算幾何学
- ユークリッド空間及びノルム空間における地帯図
- 長方形やタブローの同時配置における隅位置情報の効果
- 距離等分の存在
- DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム
- 線形計画法による非線形システムS-systemの推定
- 地図への高速ラベル貼りアルゴリズムの実装と評価
- A-12 左順序付き柔軟ラベリングの実装(画像,A.アルゴリズム・基礎)
- 電子マネーシステムにおける最適なオンラインアルゴリズム
- ヨーロッパ型及び貯蓄型アジアオプションの高精度かつ高速な価格計算
- 数値データからの直交凸領域結合ルール発見
- 領域及び区間分割を用いた決定木の作成 : 領域分割の有効性の検証
- データマイニングの最新動向 : 巨大データからの知識発見技術 (情報処理最前線)
- 平行移動する複数の点集合または線分集合に対するVoronoi図の複数さと文字配置への応用
- 距離$k$分割線と一般図形のゾーン図の存在と一意性について (理論計算機科学の深化と応用)
- RA-006 基単調領域の非交差和領域の最適イメージ切り出しアルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- TD-1-3 バイオインフォマティクスにおける知識発見
- 局所多重アライメントのための局所探索アルゴリズム : 特殊ケースにおける収束性の解析と腫瘍細胞分類への応用
- ゲノム情報解析の現状と課題
- バイオインフォマティクスへの扉
- 遺伝子制御ネットワーク解明のためのアルゴリズム (ゲノムサイエンスの新たなる挑戦) -- (第3部 ゲノム情報科学)
- 遺伝子発現制御ネットワークの論理的解析
- 配列のローカル・アラインメントの困難さについて
- 遺伝子ネットワーク解明のためのアルゴリズム
- 立体構造のマルチプルアラインメントに基づくタンパク質立体構造予測
- 東京大学医科学研究所ヒトゲノム解析センターDNA情報解析分野
- 遺伝子ネットワーク解明のためのアルゴリズム
- RNA二次構造予測のための近似アルゴリズム
- ゲノム情報解析におけるスコア関数学習の計算複雑度について
- 3.幾何的マッチングによるタンパク質立体構造の比較 (「ゲノム情報」)
- タンパク質スレッディング問題の近似について
- グラフに関する丸め問題:外平面グラフの場合
- 行列乗算とハッシュ関数を用いたブーリアンネットワークの同定アルゴリズム
- センサーネットワークの位相情報の検知に関する研究
- D-026 ジャストインタイムウェブ広告におけるタクソノミ自動生成手法(データベース,一般論文)
- 線形計画法による非線形システム S-system の推定
- ブーリアンネットワークの高速同定アルゴリズム
- 遺伝子発現パターンデータからの定性ネットワークの推定
- チェッカーボード丸めに関する考察と実装
- Image Recognition and Retrieval by Using Distance Information (Mathematical Foundations and Applications of Computer Science and Algorithms)
- タブローの最適配置問題 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 二部グラフの高濃度部分グラフ問題の近似アルゴリズムについて
- 二部グラフの高濃度部分グラフ問題の近似アルゴリズムについて
- 高次元ピラミッド構築問題とデータマイニングへの応用
- タブローの最適配置問題
- ヒッチコック型輸送問題の新算法
- 良い『メモリ図』の生成
- 曲線のピーク削減アルゴリズムの考察と実装
- F-050 数値データベースに対するエキスパート付き決定木の構築(F.人工知能)
- D-043 Web検索解析によるクラスタリング手法の研究(D.データベース)
- 曲線の最小Frechet距離近似に関するアルゴリズムの実装
- Quantum Algorithms for Intersection and Proximity Problems
- Quantum Computation in Computational Geometry
- 量子計算での幾何学データ処理
- パラメトリック最適化と計算幾何学
- MAXIMIN LOCATION OF CONVEX OBJECTS IN A POLYGON AND RELATED DYNAMIC VORONOI DIAGRAMS
- 線形計画法による遺伝情報解析のためのスコア関数の学習