平面的化学構造の正規形を計算するO(n^2)時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
化学構造を扱うデータベース・システムおよびエキスパート・システムにおいては化学構造の正規形(一意名)を計算することが重要である.化学構造の正規形は無向グラフの正規形と関係が深いが,グラフ構造が同型でもその幾何構造が異なるという立体異性体を扱わなくてはならない点が異なる.もちろん,従来から化学データベースなどで実際に用いられているアルゴリズムがあるが,それらは多項式時間アルゴリズムではない.また,多項式時間で正規形を計算する方法も存在するが複雑かつ多項式の次数が高く実用的でない。ところで,多くの化学構造は平面的なグラフ構造を持っている.本論文では,HopcroftとTarjanの平面的グラフに対する正規形計算アルゴリズムをもとに開発した,平面的グラフ構造を持つ化学構造に対するO(n^2)時間正規形計算アルゴリズムを示す.
- 一般社団法人情報処理学会の論文
- 1992-12-15
著者
関連論文
- タンパク質立体構造データベース・システムにおけるユーザインターフェースの開発
- 平面的化学構造の正規形を計算するO(n^2)時間アルゴリズム
- 91-28 理論的保証付きのメッシュ生成法
- 90-2 多角形の最適把握について
- 化学エキスパート・システム構築用ツールCHEMILOGの開発