再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法 An Efficient ZDD Construction Method Using Recuresive Specifications

この論文をさがす

著者

    • 岩下 洋哲 IWASHITA Hiroaki
    • 独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト Erato Minato Discrete Structure manipulation System Project,Japan Science and Technology Agency
    • 川原 純 KAWAHARA Jun
    • 独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト Erato Minato Discrete Structure manipulation System Project,Japan Science and Technology Agency
    • 湊 真一 MINATO Shin-ichi
    • 独立行政法人科学技術振興機構ERATO湊離散構造処理系プロジェクト Erato Minato Discrete Structure manipulation System Project,Japan Science and Technology Agency

抄録

近年、グラフ上の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.

収録刊行物

  • 電子情報通信学会技術研究報告. VLD, VLSI設計技術

    電子情報通信学会技術研究報告. VLD, VLSI設計技術 112(320), 25-29, 2012-11-19

    一般社団法人電子情報通信学会

参考文献:  11件中 1-11件 を表示

各種コード

  • NII論文ID(NAID)
    110009641720
  • NII書誌ID(NCID)
    AN10013323
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    0913-5685
  • NDL 記事登録ID
    024148797
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ