WEKO3
アイテム
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
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
要旨・審査要旨 (502.1 kB)
|
||
|
本文 (816.7 kB)
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2010-02-22 | |||||
| タイトル | ||||||
| タイトル | Studies on Subgraph and Supergraph Enumeration Algorithms | |||||
| タイトル | ||||||
| タイトル | Studies on Subgraph and Supergraph Enumeration Algorithms | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | 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 | |||||
