平面的化学構造の正規形を計算するO (n2)時間アルゴリズム

書誌事項

タイトル別名
  • An O (n2) Time Algorithm for Computing a Canonical Form of a Chemical Structure Which Has a Planar Graph Structure
  • 基礎理論

この論文をさがす

抄録

化学構造を扱うデータベース・システムおよびエキスパート・システムにおいては化学構造の正規形(一意名)を計算することが重要である.化学構造の正規形は無向グラフの正規形と関係が深いが グラフ構造が同型でもその幾何構造が異なるという立体異性体を扱わなくてはならない点が異なる.もちろん 従来から化学データベースなどで実際に用いられているアルゴリズムがあるが それらは多項式時間アルゴリズムではない.また 多項式時間で正規形を計算する方法も存在するが複雑かつ多項式の次数が高く実用的でない。ところで 多くの化学構造は平面的なグラフ構造を持っている.本論文では HopcroftとTarjanの平面的グラフに対する正規形計算アルゴリズムをもとに開発した 平面的グラフ構造を持つ化学構造に対するO(n^2)時間正規形計算アルゴリズムを示す.

収録刊行物

参考文献 (12)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1050564287841306496
  • NII論文ID
    110002764712
  • NII書誌ID
    AN00116647
  • ISSN
    18827764
  • Web Site
    http://id.nii.ac.jp/1001/00014588/
  • 本文言語コード
    ja
  • 資料種別
    journal article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ