| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-11-26 10:55 再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法 ○岩下洋哲・川原 純（JST/北大）・湊 真一（北大/JST）  VLD2012-63 DC2012-29 |
|
| 抄録 | （和） | 近年、グラフ上の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 / / / | |
| 文献情報 | 信学技報, vol. 112, no. 320, VLD2012-63, pp. 25-29, 2012年11月. | |
| 資料番号 | VLD2012-63 | |
| 発行日 | 2012-11-19 (VLD, DC) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | VLD2012-63 DC2012-29 |
|
| 研究会情報 | |
| 研究会 | VLD DC IPSJ-SLDM CPSY RECONF ICD CPM |
| 開催期間 | 2012-11-26 - 2012-11-28 |
| 開催地（和） | 九州大学百年講堂 |
| 開催地（英） | Centennial Hall Kyushu University School of Medicine |
| テーマ（和） | デザインガイア2012 -VLSI設計の新しい大地- |
| テーマ（英） | Design Gaia 2012 -New Field of VLSI Design- |
| 講演論文情報の詳細 | |
| 申込み研究会 | VLD |
| 会議コード | 2012-11-VLD-DC-SLDM-CPSY-RECONF-ICD-CPM |
| 本文の言語 | 日本語 |
| タイトル（和） | 再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法 |
| サブタイトル（和） | |
| タイトル（英） | An Efficient ZDD Construction Method Using Recursive Specifications |
| サブタイトル（英） | |
| キーワード(1)（和/英） | フロンティア法 / frontier-based search |
| キーワード(2)（和/英） | ZDD / ZDD |
| キーワード(3)（和/英） | 部分グラフの列挙 / subgraph enumeration |
| キーワード(4)（和/英） | リンクパズル / link puzzle |
| キーワード(5)（和/英） | 遅延評価 / lazy evaluation |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岩下 洋哲 / Hiroaki Iwashita / イワシタ ヒロアキ |
| 第1著者 所属（和/英） | 科学技術振興機構 (略称： JST/北大) Japan Science and Technology Agency (略称： JST) |
| 第2著者 氏名（和/英/ヨミ） | 川原 純 / Jun Kawahara / カワハラ ジュン |
| 第2著者 所属（和/英） | 科学技術振興機構 (略称： JST/北大) Japan Science and Technology Agency (略称： JST) |
| 第3著者 氏名（和/英/ヨミ） | 湊 真一 / Shin-ichi Minato / |
| 第3著者 所属（和/英） | 北海道大学 (略称： 北大/JST) Hokkaido University (略称： Hokkaido Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-11-26 10:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | VLD |
| 資料番号 | VLD2012-63, DC2012-29 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.320(VLD), no.321(DC) |
| ページ範囲 | pp.25-29 |
| ページ数 | 5 |
| 発行日 | 2012-11-19 (VLD, DC) |
[研究会発表申込システムのトップページに戻る]