書誌事項
- タイトル別名
-
- 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)時間正規形計算アルゴリズムを示す.
収録刊行物
-
- 情報処理学会論文誌
-
情報処理学会論文誌 33 (12), 1487-1496, 1992-12-15
一般社団法人情報処理学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- 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