WEKO3
-
RootNode
アイテム
K-縮退グラフに含まれる誘導木の列挙
https://ipsj.ixsq.nii.ac.jp/records/101704
https://ipsj.ixsq.nii.ac.jp/records/10170445fc7eb2-8c99-4fe3-8503-91c6bf058d26
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL14148017.pdf (694.8 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-06-06 | |||||||
| タイトル | ||||||||
| タイトル | K-縮退グラフに含まれる誘導木の列挙 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Enumeration of Induced Subtrees in a K-Degenerate Graph | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 北海道大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 北海道大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 国立情報学研究所 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hokkaido University, Graduate School of Information Science and Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hokkaido University, Graduate School of Information Science and Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| National Institute of Informatics | ||||||||
| 著者名 |
和佐, 州洋
有村, 博紀
宇野, 毅明
× 和佐, 州洋 有村, 博紀 宇野, 毅明
|
|||||||
| 著者名(英) |
Kunihiro, Wasa
Hiroki, Arimura
Takeaki, Uno
× Kunihiro, Wasa Hiroki, Arimura Takeaki, Uno
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本稿では，k- 縮退グラフに含まれる誘導木 （連結かつ非巡回な誘導部分グラフ） を，効率よく列挙するアルゴリズムを与える．グラフ G=(V，E) が k-縮退 （k-degenerate） であるとは，G の任意の部分グラフが高々 k の次数を持つ頂点を含むときをいう．これまで，制約のある誘導部分グラフの列挙に関しては，連結な誘導グラフ （Avis，Fukuda，DAM，1996） や，コードレスパス，コードレスサイクル （宇野，第 92 回アルゴリズム研究会，2003） の列挙に関する先行研究があるが，誘導木については知られていない．最大次数が d のとき，誘導木 1 つ当たり O(d) 遅延の列挙アルゴリズムは容易に構成できるが，これをどの程度まで改善できるかは未解決の問題である．我々のアルゴリズムは，入力グラフ G が k- 縮退グラフであるとき，誘導木を 1 つ当たりならし O(k) 時間で列挙する．系として，k が定数ならば，誘導木を 1 つたり，ならし定数時間で列挙可能である． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2014-AL-148, 号 17, p. 1-6, 発行日 2014-06-06 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
