WEKO3
アイテム
線形サイズ<i>k</i>-IBDD充足可能性問題に対する厳密アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/113207
https://ipsj.ixsq.nii.ac.jp/records/113207697ea564-a1ae-4dec-9239-81967a60d836
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL15152001.pdf (736.2 kB)
|
Copyright (c) 2015 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2015-02-24 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 線形サイズ<i>k</i>-IBDD充足可能性問題に対する厳密アルゴリズム | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 成蹊大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 国立情報学研究所／JST, ERATO, 河原林巨大グラフプロジェクト | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学／日本学術振興会 | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Seikei University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| National Institute of Informatics / JST, ERATO, Kawarabayashi Large Graph Project | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Kyoto University / Japan Society for the Promotion of Science | ||||||||||||
| 著者名 |
脊戸, 和寿
× 脊戸, 和寿
× 照山, 順一
× 長尾, 篤樹
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | k-IBDD は，k 段のレイヤーを持つ分岐プログラムであり，各レイヤーが OBDD (順序付き二分決定図) となっている．本稿では，k-IBDD 充足可能性問題 （以下，k-IBDD SAT） を考える．k-IBDD SAT とは，与えられた k-IBDD が 1 を出力するような変数割当が存在するかどうかを判定する問題である．本問題に対して，n 変数，poly(n) ノードの k-IBDD SAT を高々 poly(n)・2n-n1/2k-1 時間で解く多項式領域アルゴリズムが知られている．ここで，poly(n) は n の多項式を表す．本稿では，n 変数，cn ノードの k-IBDD SAT を高々 poly(n)・2(1-μ(c))n 時間で解く指数領域アルゴリズムを与える．ここで，μ(c)=Ω(1/(log c)2k-1-1) である．我々のアルゴリズムは既存のアルゴリズムを拡張することで線形サイズの k-IBDD に対して 2n 時間より指数的な高速化を達成している． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN1009593X | |||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2015-AL-152, 号 1, p. 1-7, 発行日 2015-02-24 |
|||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
