| 講演名 | 2012-11-26 再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法(システム設計技術(1),デザインガイア2012-VLSI設計の新しい大地-) 岩下 洋哲, 川原 純, 湊 真一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年、グラフ上の2点間の全てのパスを表現したZero-suppressed Binary Decision Diagram(ZDD)を高速に構築するアルゴリズムがKnuthによって発表され、ZDDを用いた新たな列挙手法が注目を集めている。この手法に基づいたこれまでのアプリケーションの多くでは、構築されたZDDに対して様々な条件によるフィルタリングを行って最終的に必要な結果を取り出している。この計算中に発生しやすいメモリ爆発を避けるため、我々は、中間的なZDD構造を構築することなく最終的なZDD構造を直接構築する手法を提案する。 |
| 抄録(英) | 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. |
| キーワード(和) | フロンティア法 / ZDD / 部分グラフの列挙 / リンクパズル / 遅延評価 |
| キーワード(英) | frontier-based search / ZDD / subgraph enumeration / link puzzle / lazy evaluation |
| 資料番号 | VLD2012-63,DC2012-29 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2012/11/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法(システム設計技術(1),デザインガイア2012-VLSI設計の新しい大地-) |
| サブタイトル（和） | |
| タイトル（英） | An Efficient ZDD Construction Method Using Recuresive Specifications |
| サブタイトル（和） | |
| キーワード(1)（和/英） | フロンティア法 / frontier-based search |
| キーワード(2)（和/英） | ZDD / ZDD |
| キーワード(3)（和/英） | 部分グラフの列挙 / subgraph enumeration |
| キーワード(4)（和/英） | リンクパズル / link puzzle |
| キーワード(5)（和/英） | 遅延評価 / lazy evaluation |
| 第 1 著者 氏名（和/英） | 岩下 洋哲 / Hiroaki IWASHITA |
| 第 1 著者 所属（和/英） | 独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト:北海道大学大学院情報科学研究科 ERATO Minato Discrete Structure Manipulation System Project, Japan Science and Technology Agency:Graduate School of Information Science and Technology, Hokkaido University |
| 第 2 著者 氏名（和/英） | 川原 純 / Jun KAWAHARA |
| 第 2 著者 所属（和/英） | 独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト:北海道大学大学院情報科学研究科 ERATO Minato Discrete Structure Manipulation System Project, Japan Science and Technology Agency:Graduate School of Information Science and Technology, Hokkaido University |
| 第 3 著者 氏名（和/英） | 湊 真一 / Shin-ichi MINATO |
| 第 3 著者 所属（和/英） | 北海道大学大学院情報科学研究科:独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト Graduate School of Information Science and Technology, Hokkaido University:ERATO Minato Discrete Structure Manipulation System Project, Japan Science and Technology Agency |
| 発表年月日 | 2012-11-26 |
| 資料番号 | VLD2012-63,DC2012-29 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 320 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |