@techreport{oai:ipsj.ixsq.nii.ac.jp:00102915,
 author = {脊戸和寿 and 照山順一 and 長尾篤樹},
 issue = {9},
 month = {Sep},
 note = {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 時間で解く多項式領域アルゴリズムを与える．},
 title = {<i>k</i>-IBDD充足可能性問題に対する厳密アルゴリズム},
 year = {2014}
}