WEKO3
アイテム
{"_buckets": {"deposit": "609807ba-38f2-42d2-9730-32cb633559ff"}, "_deposit": {"created_by": 1, "id": "853", "owners": [1], "pid": {"revision_id": 0, "type": "depid", "value": "853"}, "status": "published"}, "_oai": {"id": "oai:ir.soken.ac.jp:00000853", "sets": ["19"]}, "author_link": ["0", "0", "0"], "item_1_biblio_info_21": {"attribute_name": "書誌情報(ソート用)", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2006-09-29", "bibliographicIssueDateType": "Issued"}, "bibliographic_titles": [{}]}]}, "item_1_creator_2": {"attribute_name": "著者名", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "清見, 礼"}], "nameIdentifiers": [{"nameIdentifier": "0", "nameIdentifierScheme": "WEKO"}]}]}, "item_1_creator_3": {"attribute_name": "フリガナ", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "キヨミ, マサシ"}], "nameIdentifiers": [{"nameIdentifier": "0", "nameIdentifierScheme": "WEKO"}]}]}, "item_1_date_granted_11": {"attribute_name": "学位授与年月日", "attribute_value_mlt": [{"subitem_dategranted": "2006-09-29"}]}, "item_1_degree_grantor_5": {"attribute_name": "学位授与機関", "attribute_value_mlt": [{"subitem_degreegrantor": [{"subitem_degreegrantor_name": "総合研究大学院大学"}]}]}, "item_1_degree_name_6": {"attribute_name": "学位名", "attribute_value_mlt": [{"subitem_degreename": "博士(情報学)"}]}, "item_1_description_1": {"attribute_name": "ID", "attribute_value_mlt": [{"subitem_description": "2006518", "subitem_description_type": "Other"}]}, "item_1_description_12": {"attribute_name": "要旨", "attribute_value_mlt": [{"subitem_description": " Enumeration is listing all objects that satisfy given properties. We call\u003cbr /\u003eenumeration of subgraphs of a given graph, such that those subgraphs have\u003cbr /\u003especified properties, as subgraph enumeration. Similarly We call enumeration\u003cbr /\u003eof supergraphs of a given graph as subgraph enumeration. In this thesis, we will\u003cbr /\u003econsider about subgraph/supergraph enumeration algorithms. In areas such as\u003cbr /\u003edata mining or statistics, subgraph enumeration and supergraph enumeration\u003cbr /\u003eplay important roles to find frequent patterns or to draw on some rules satisfied\u003cbr /\u003eby the inputs, etc.\u003cbr /\u003e We developed two types of algorithms of subgraph/supergraph enumeration\u003cbr /\u003efor chordal and related graphs; one searches graphs to be enumerated by an\u003cbr /\u003eedge addition or an edge removal; the other defines a neighbor of searching by\u003cbr /\u003ea simplicial vertex elimination, which is specific for chordal graphs. The first\u003cbr /\u003etype uses the fact that there are only O(n\u003csup\u003e2\u003c/sup\u003e) edges in a complete graph K\u003csub\u003en\u003c/sub\u003e,\u003cbr /\u003eand achieves polynomial time delay algorithms. We can use this method to\u003cbr /\u003edevelop both subgraph enumeration algorithms and super graph enumeration\u003cbr /\u003ealgorithms. The second type uses nice properties of simplicial vertices and the\u003cbr /\u003efact that we can enumerate cliques in a chordal graph quickly. Using this type\u003cbr /\u003eof algorithm for chordal subgraph enumeration is faster than doing so using\u003cbr /\u003ethe first type (it needs only constant time to enumerate each chordal graph).\u003cbr /\u003eHowever, this method is only for the subgraph enumeration.\u003cbr /\u003e The organization of this thesis is as follows. We first introduce enumeration,\u003cbr /\u003efocusing particularly on graph enumeration. Chapter 2 provides the preliminaries,\u003cbr /\u003enotes about terms that we use in this thesis, and explanations about graph\u003cbr /\u003eclasses. In Chapter 3, we discuss the difficulties of our enumeration problems,\u003cbr /\u003eand explain the framework of the reverse search method. In Chapter 4, we\u003cbr /\u003edevelop algorithms for our enumeration problems. These algorithms are based\u003cbr /\u003eon the reverse search method. They are of two types: one defines parents such\u003cbr /\u003ethat the difference between a graph and its parent is exactly one, and the other\u003cbr /\u003edefines parents such that the parent of a graph is obtained by eliminating a\u003cbr /\u003esimplicial vertex. And, we conclude the thesis in Chapter 5.", "subitem_description_type": "Other"}]}, "item_1_description_18": {"attribute_name": "フォーマット", "attribute_value_mlt": [{"subitem_description": "application/pdf", "subitem_description_type": "Other"}]}, "item_1_description_7": {"attribute_name": "学位記番号", "attribute_value_mlt": [{"subitem_description": "総研大甲第998号", "subitem_description_type": "Other"}]}, "item_1_select_14": {"attribute_name": "所蔵", "attribute_value_mlt": [{"subitem_select_item": "有"}]}, "item_1_select_8": {"attribute_name": "研究科", "attribute_value_mlt": [{"subitem_select_item": "複合科学研究科"}]}, "item_1_select_9": {"attribute_name": "専攻", "attribute_value_mlt": [{"subitem_select_item": "17 情報学専攻"}]}, "item_1_text_10": {"attribute_name": "学位授与年度", "attribute_value_mlt": [{"subitem_text_value": "2006"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "KIYOMI, Masashi", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "0", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2016-02-17"}], "displaytype": "simple", "download_preview_message": "", "file_order": 0, "filename": "甲998_要旨.pdf", "filesize": [{"value": "502.1 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_11", "mimetype": "application/pdf", "size": 502100.0, "url": {"label": "要旨・審査要旨", "url": "https://ir.soken.ac.jp/record/853/files/甲998_要旨.pdf"}, "version_id": "2c155814-ce22-48f0-a379-113b096bca7d"}, {"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2016-02-17"}], "displaytype": "simple", "download_preview_message": "", "file_order": 1, "filename": "甲998_本文.pdf", "filesize": [{"value": "816.7 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_11", "mimetype": "application/pdf", "size": 816700.0, "url": {"label": "本文", "url": "https://ir.soken.ac.jp/record/853/files/甲998_本文.pdf"}, "version_id": "2dcc7216-32f1-4709-8613-0fb33e360133"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "thesis", "resourceuri": "http://purl.org/coar/resource_type/c_46ec"}]}, "item_title": "Studies on Subgraph and Supergraph Enumeration Algorithms", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Studies on Subgraph and Supergraph Enumeration Algorithms"}, {"subitem_title": "Studies on Subgraph and Supergraph Enumeration Algorithms", "subitem_title_language": "en"}]}, "item_type_id": "1", "owner": "1", "path": ["19"], "permalink_uri": "https://ir.soken.ac.jp/records/853", "pubdate": {"attribute_name": "公開日", "attribute_value": "2010-02-22"}, "publish_date": "2010-02-22", "publish_status": "0", "recid": "853", "relation": {}, "relation_version_is_last": true, "title": ["Studies on Subgraph and Supergraph Enumeration Algorithms"], "weko_shared_id": -1}
Studies on Subgraph and Supergraph Enumeration Algorithms
https://ir.soken.ac.jp/records/853
https://ir.soken.ac.jp/records/85368ff5385-3e68-414b-a4b3-590a4078afc8
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
||
![]() |
Item type | 学位論文 / Thesis or Dissertation(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2010-02-22 | |||||
タイトル | ||||||
タイトル | Studies on Subgraph and Supergraph Enumeration Algorithms | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | Studies on Subgraph and Supergraph Enumeration Algorithms | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||
資源タイプ | thesis | |||||
著者名 |
清見, 礼
× 清見, 礼 |
|||||
フリガナ |
キヨミ, マサシ
× キヨミ, マサシ |
|||||
著者 |
KIYOMI, Masashi
× KIYOMI, Masashi |
|||||
学位授与機関 | ||||||
学位授与機関名 | 総合研究大学院大学 | |||||
学位名 | ||||||
学位名 | 博士(情報学) | |||||
学位記番号 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 総研大甲第998号 | |||||
研究科 | ||||||
値 | 複合科学研究科 | |||||
専攻 | ||||||
値 | 17 情報学専攻 | |||||
学位授与年月日 | ||||||
学位授与年月日 | 2006-09-29 | |||||
学位授与年度 | ||||||
2006 | ||||||
要旨 | ||||||
内容記述タイプ | Other | |||||
内容記述 | Enumeration is listing all objects that satisfy given properties. We call<br />enumeration of subgraphs of a given graph, such that those subgraphs have<br />specified properties, as subgraph enumeration. Similarly We call enumeration<br />of supergraphs of a given graph as subgraph enumeration. In this thesis, we will<br />consider about subgraph/supergraph enumeration algorithms. In areas such as<br />data mining or statistics, subgraph enumeration and supergraph enumeration<br />play important roles to find frequent patterns or to draw on some rules satisfied<br />by the inputs, etc.<br /> We developed two types of algorithms of subgraph/supergraph enumeration<br />for chordal and related graphs; one searches graphs to be enumerated by an<br />edge addition or an edge removal; the other defines a neighbor of searching by<br />a simplicial vertex elimination, which is specific for chordal graphs. The first<br />type uses the fact that there are only O(n<sup>2</sup>) edges in a complete graph K<sub>n</sub>,<br />and achieves polynomial time delay algorithms. We can use this method to<br />develop both subgraph enumeration algorithms and super graph enumeration<br />algorithms. The second type uses nice properties of simplicial vertices and the<br />fact that we can enumerate cliques in a chordal graph quickly. Using this type<br />of algorithm for chordal subgraph enumeration is faster than doing so using<br />the first type (it needs only constant time to enumerate each chordal graph).<br />However, this method is only for the subgraph enumeration.<br /> The organization of this thesis is as follows. We first introduce enumeration,<br />focusing particularly on graph enumeration. Chapter 2 provides the preliminaries,<br />notes about terms that we use in this thesis, and explanations about graph<br />classes. In Chapter 3, we discuss the difficulties of our enumeration problems,<br />and explain the framework of the reverse search method. In Chapter 4, we<br />develop algorithms for our enumeration problems. These algorithms are based<br />on the reverse search method. They are of two types: one defines parents such<br />that the difference between a graph and its parent is exactly one, and the other<br />defines parents such that the parent of a graph is obtained by eliminating a<br />simplicial vertex. And, we conclude the thesis in Chapter 5. | |||||
所蔵 | ||||||
値 | 有 | |||||
フォーマット | ||||||
内容記述タイプ | Other | |||||
内容記述 | application/pdf |