WEKO3
アイテム
再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法
https://ipsj.ixsq.nii.ac.jp/records/86935
https://ipsj.ixsq.nii.ac.jp/records/86935f3d43963-2323-4568-ac50-9cb9e83637c6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-SLDM12158005.pdf (364.8 kB)
2100年1月1日からダウンロード可能です。
|
Copyright (c) 2012 by the Institute of Electronics, Information and Communication Engineers
This SIG report is only available to those in membership of the SIG. |
|
| SLDM:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-11-19 | |||||||
| タイトル | ||||||||
| タイトル | 再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An Efficient ZDD Construction Method Using Recuresive Specifications | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | システム設計技術 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト／北海道大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト／北海道大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 北海道大学大学院情報科学研究科／独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| ERATO Minato Discrete Structure Manipulation System Project, Japan Science and Technology Agency / Graduate School of Information Science and Technology, Hokkaido University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| ERATO Minato Discrete Structure Manipulation System Project, Japan Science and Technology Agency / Graduate School of Information Science and Technology, Hokkaido University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Science and Technology, Hokkaido University / ERATO Minato Discrete Structure Manipulation System Project, Japan Science and Technology Agency | ||||||||
| 著者名 |
岩下, 洋哲
× 岩下, 洋哲
|
|||||||
| 著者名(英) |
Hiroaki, Iwashita
× Hiroaki, Iwashita
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 近年，グラフ上の 2 点間の全てのパスを表現した Zero-supprcssed Binary Decision Diagram (ZDD) を高速に構築するアルゴリズムが Knuth によって発表され，ZDD を用いた新たな列挙手法が注目を集めている．この手法に基づいたこれまでのアプリケーションの多くでは，構築された ZDD に対して様々な条件によるフィルタリングを行って最終的に必要な結果を取り出している．この計算中に発生しやすいメモリ爆発を避けるため，我々は，中間的な ZDD 構造を構築することなく最終的な ZDD 構造を直接構築する手法を提案する． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In recent years, new enumeration methods using zero-suppressed binary decision diagrams (ZDDs) has been attracting attention since Kunuth introduced a very fast algorithm to construct a ZDD representing all paths between two vertices in a graph. Many of the application so far based on this approach compute the final results by filtering out unnecessary cases from the constructed ZDDs. To avoid memory explosion in this computation, we propose a method to get the final ZDDs without constructing any intermediate ZDDs. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11451459 | |||||||
| 書誌情報 |
研究報告システムLSI設計技術（SLDM） 巻 2012-SLDM-158, 号 5, p. 1-5, 発行日 2012-11-19 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
