WEKO3
アイテム
真区間グラフの高速な列挙アルゴリズムとその応用
https://ipsj.ixsq.nii.ac.jp/records/212246
https://ipsj.ixsq.nii.ac.jp/records/212246547b1a15-adf2-46fa-9ee8-568d92ddcc10
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL21184007.pdf (2.9 MB)
|
Copyright (c) 2021 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-08-18 | |||||||||
| タイトル | ||||||||||
| タイトル | 真区間グラフの高速な列挙アルゴリズムとその応用 | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 九州工業大学 | ||||||||||
| 著者所属 | ||||||||||
| 九州工業大学 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Kyushu Institute of Technology | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Kyushu Institute of Technology | ||||||||||
| 著者名 |
武田, 浩和
× 武田, 浩和
× 斎藤, 寿樹
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 区間グラフは区間の集合を表現に持つグラフである．真区間グラフは区間グラフの部分クラスで，どの区間も他のどの区間とも包含関係にない区間の集合を表現に持つグラフである．グラフ同型性を考慮した真区間グラフの列挙アルゴリズムとして逆探索法を用いたものが知られている．このアルゴリズムはグラフ 1 つあたりの出力に O(1) 時間で，理論的に効率的であるものの，グラフの頂点数が大きくなると真区間グラフの数は膨大となり，すべてを出力することはできない．一方で，ゼロサプレス型二分決定グラフ (ZDD) は組み合わせ集合をコンパクトに表現できるデータ構造で，最適化問題や列挙問題を効率的に処理できるとして近年，注目を集めている．本研究では ZDD を用いた真区間グラフを高速に列挙するアルゴリズムを提案する．提案アルゴリズムすべての真区間グラフを表現する ZDD を頂点数 n の多項式時間・領域で構築する．これまでの逆探索法では実験的に頂点数 n=18 までしか列挙できなかったのに対し，提案アルゴリズムでは n=700 の真区間グラフを容易に計算可能となる．また本アルゴリズムは，頂点数だけでなく，最大クリークサイズや辺の本数などの制約を加えた真区間グラフもわずかな拡張によって列挙することができる．本稿ではこれらのアルゴリズムを解析するとともに，計算機実験によりその効率性を示す． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2021-AL-184, 号 7, p. 1-8, 発行日 2021-08-18 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
