BDD/ZDDを用いたグラフ列挙索引化技法

この論文をさがす

著者

抄録

本稿では,与えられたグラフ構造のなかから,ある制約条件を満たすような部分グラフ構造をすべて列挙し,それらをBDD/ZDDを用いて圧縮表現して索引化する技法について述べる.まず,BDD/ZDDとその演算処理系について簡単に説明し,次に,ZDDを用いた高速なパス列挙索引化アルゴリズムSimpathの概要を解説する.このアルゴリズムはKnuthが近年提案したものであるが,制約条件によって多くのバリエーションが存在することから,われわれはそれらを総称して「フロンティア法」と呼んでいる.本稿ではフロンティア法がなぜ高速であるか,そして従来のBDD/ZDDを用いた制約充足問題の解法との違いについて述べる.

収録刊行物

  • オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch

    オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch 57(11), 597-603, 2012-11-01

    公益社団法人日本オペレーションズ・リサーチ学会

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

被引用文献:  2件中 1-2件 を表示

キーワード

各種コード

  • NII論文ID(NAID)
    110009544486
  • NII書誌ID(NCID)
    AN00364999
  • 本文言語コード
    JPN
  • 資料種別
    REV
  • ISSN
    00303674
  • NDL 記事登録ID
    024069911
  • NDL 請求記号
    Z4-108
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS 
ページトップへ