<i>k</i>-IBDD充足可能性問題に対する厳密アルゴリズム

• 脊戸和寿

  成蹊大学

• 照山順一

  国立情報学研究所|JST, ERATO, 河原林巨大グラフプロジェクト

• 長尾篤樹

  京都大学|日本学術振興会特別研究員DC

抄録

k-IBDD は,k 段のレイヤーを持つ分岐プログラムであり,各レイヤーが OBDD (順序付き二分決定図) となっている.本稿では,k-IBDD 充足可能性問題 (以下,k-IBDD SAT) を考える.k-IBDD SAT とは,入力として k-IBDD が与えられ,シンク 1 に到達する変数への割当が存在するかどうかを判定する問題である.本稿では,n 変数,poly(n) ノードの 2-IBDD SAT を高々 poly(n)・2n-√n 時間で解く多項式領域アルゴリズムを与える.poly(n) は n の多項式を表す.さらに,このアルゴリズムを拡張することにより,n 変数,poly(n) ノードの k-IBDD SAT を高々,poly(n)・2n-n1/2k-1 時間で解く多項式領域アルゴリズムを与える.

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 2014 (9), 1-6, 2014-09-05

  一般社団法人情報処理学会

詳細情報

• CRID: 1571417127834881664
• NII論文ID: 110009821036
• NII書誌ID: AN1009593X
• ISSN: 09196072
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles