WEKO3
アイテム
{"_buckets": {"deposit": "793f2aa7-af75-4a70-9d42-27455f9f4fbf"}, "_deposit": {"created_by": 4, "id": "28", "owners": [4], "pid": {"revision_id": 0, "type": "depid", "value": "28"}, "status": "published"}, "_oai": {"id": "oai:tiu-tijc.repo.nii.ac.jp:00000028", "sets": ["54"]}, "author_link": ["24"], "item_3_biblio_info_12": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "1996-03-25", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "47", "bibliographicPageStart": "37", "bibliographicVolumeNumber": "2", "bibliographic_titles": [{"bibliographic_title": "研究紀要"}, {"bibliographic_title": "Bulletin of Tsukuba International University", "bibliographic_titleLang": "en"}]}]}, "item_3_description_10": {"attribute_name": "抄録(日)", "attribute_value_mlt": [{"subitem_description": "化学構造の検索は様々な分野で重要な意味をもつ。一方、グラフ理論では、このような検索はNP問題として証明されたグラフの部分一致判定という操作になる。グラフの部分一致判定を極力さけるために化学構造を部分順序構造(DAG)に構築して、部分一致判定を同形判定に簡単化することを提案する。本論文では同形判定の効果的なアルゴリズムを提案する。", "subitem_description_type": "Other"}]}, "item_3_description_11": {"attribute_name": "抄録(英)", "attribute_value_mlt": [{"subitem_description": "The chemical structure searching is one of the most important subjects in many fields. On the other hand, structure searching is a graph isomorphism problem of testing subgraph, which has been proved to be NP-complete and should be avoided if possible. For this purpose, our proposal is to organize the chemical structure by pre-processing to a semi-order structure (a DAG, Directed Acyclic Graph), where each chemical structure has all its sub-structures as its super nodes in the DAG. With this DAG, subgraph searching is simplified to exact graph determination. When a graph is found to be isomorphic to the query graph, then the sub-DAG rooted at the found graph is the answer to the query. In this paper, we propose an improved polynomial-time algorithm for the graph isomorphism problem.", "subitem_description_type": "Other"}]}, "item_3_description_15": {"attribute_name": "表示順", "attribute_value_mlt": [{"subitem_description": "7", "subitem_description_type": "Other"}]}, "item_3_description_16": {"attribute_name": "アクセション番号", "attribute_value_mlt": [{"subitem_description": "KJ00004010956", "subitem_description_type": "Other"}]}, "item_3_description_2": {"attribute_name": "ページ属性", "attribute_value_mlt": [{"subitem_description": "P", "subitem_description_type": "Other"}]}, "item_3_identifier_registration": {"attribute_name": "ID登録", "attribute_value_mlt": [{"subitem_identifier_reg_text": "10.20843/00000022", "subitem_identifier_reg_type": "JaLC"}]}, "item_3_source_id_1": {"attribute_name": "雑誌書誌ID", "attribute_value_mlt": [{"subitem_source_identifier": "AN10480238", "subitem_source_identifier_type": "NCID"}]}, "item_3_source_id_19": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "13412099", "subitem_source_identifier_type": "ISSN"}]}, "item_3_text_3": {"attribute_name": "論文名よみ", "attribute_value_mlt": [{"subitem_text_value": "An Isomorphism Algorithm for Chemical Graph Searching"}]}, "item_3_text_6": {"attribute_name": "著者所属(日)", "attribute_value_mlt": [{"subitem_text_value": "つくば国際大学産業情報学科"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Chen, Hanxiong", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "24", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2017-09-04"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "KJ00004010956.pdf", "filesize": [{"value": "568.0 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 568000.0, "url": {"label": "KJ00004010956.pdf", "url": "https://tiu-tijc.repo.nii.ac.jp/record/28/files/KJ00004010956.pdf"}, "version_id": "efae10d9-2aaa-4ee8-9566-b42245d6f16f"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "algorithm", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "chemical structure", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "isomorphic", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "retrieve /", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "departmental bulletin paper", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "An Isomorphism Algorithm for Chemical Graph Searching", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "An Isomorphism Algorithm for Chemical Graph Searching", "subitem_title_language": "en"}]}, "item_type_id": "3", "owner": "4", "path": ["54"], "permalink_uri": "https://doi.org/10.20843/00000022", "pubdate": {"attribute_name": "公開日", "attribute_value": "2017-09-04"}, "publish_date": "2017-09-04", "publish_status": "0", "recid": "28", "relation": {}, "relation_version_is_last": true, "title": ["An Isomorphism Algorithm for Chemical Graph Searching"], "weko_shared_id": -1}
An Isomorphism Algorithm for Chemical Graph Searching
https://doi.org/10.20843/00000022
https://doi.org/10.20843/0000002232112c9c-1377-4c59-a84b-e66acf036260
名前 / ファイル | ライセンス | アクション |
---|---|---|
KJ00004010956.pdf (568.0 kB)
|
|
Item type | [ELS]紀要論文 / Departmental Bulletin Paper(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2017-09-04 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | An Isomorphism Algorithm for Chemical Graph Searching | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | algorithm | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | chemical structure | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | isomorphic | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | retrieve / | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
資源タイプ | departmental bulletin paper | |||||
ID登録 | ||||||
ID登録 | 10.20843/00000022 | |||||
ID登録タイプ | JaLC | |||||
雑誌書誌ID | ||||||
収録物識別子タイプ | NCID | |||||
収録物識別子 | AN10480238 | |||||
ページ属性 | ||||||
内容記述タイプ | Other | |||||
内容記述 | P | |||||
論文名よみ | ||||||
An Isomorphism Algorithm for Chemical Graph Searching | ||||||
著者 |
Chen, Hanxiong
× Chen, Hanxiong |
|||||
著者所属(日) | ||||||
つくば国際大学産業情報学科 | ||||||
抄録(日) | ||||||
内容記述タイプ | Other | |||||
内容記述 | 化学構造の検索は様々な分野で重要な意味をもつ。一方、グラフ理論では、このような検索はNP問題として証明されたグラフの部分一致判定という操作になる。グラフの部分一致判定を極力さけるために化学構造を部分順序構造(DAG)に構築して、部分一致判定を同形判定に簡単化することを提案する。本論文では同形判定の効果的なアルゴリズムを提案する。 | |||||
抄録(英) | ||||||
内容記述タイプ | Other | |||||
内容記述 | The chemical structure searching is one of the most important subjects in many fields. On the other hand, structure searching is a graph isomorphism problem of testing subgraph, which has been proved to be NP-complete and should be avoided if possible. For this purpose, our proposal is to organize the chemical structure by pre-processing to a semi-order structure (a DAG, Directed Acyclic Graph), where each chemical structure has all its sub-structures as its super nodes in the DAG. With this DAG, subgraph searching is simplified to exact graph determination. When a graph is found to be isomorphic to the query graph, then the sub-DAG rooted at the found graph is the answer to the query. In this paper, we propose an improved polynomial-time algorithm for the graph isomorphism problem. | |||||
書誌情報 |
研究紀要 en : Bulletin of Tsukuba International University 巻 2, p. 37-47, 発行日 1996-03-25 |
|||||
表示順 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 7 | |||||
アクセション番号 | ||||||
内容記述タイプ | Other | |||||
内容記述 | KJ00004010956 | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 13412099 |