WEKO3
アイテム
<i>k</i>-IBDD充足可能性問題に対する厳密アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/102915
https://ipsj.ixsq.nii.ac.jp/records/102915f6b225ff-d188-4062-b1a1-ee62bebb9eb9
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL14149009.pdf (874.2 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-09-05 | |||||||
| タイトル | ||||||||
| タイトル | <i>k</i>-IBDD充足可能性問題に対する厳密アルゴリズム | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 成蹊大学 | ||||||||
| 著者所属 | ||||||||
| 国立情報学研究所／JST, ERATO, 河原林巨大グラフプロジェクト | ||||||||
| 著者所属 | ||||||||
| 京都大学／日本学術振興会特別研究員DC | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Seikei University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| National Institute of Informatics / JST, ERATO, Kawarabayashi Large Graph Project | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyoto University / Research Fellow of 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) ノードの 2-IBDD SAT を高々 poly(n)・2n-√n 時間で解く多項式領域アルゴリズムを与える．poly(n) は n の多項式を表す．さらに，このアルゴリズムを拡張することにより，n 変数，poly(n) ノードの k-IBDD SAT を高々，poly(n)・2n-n1/2k-1 時間で解く多項式領域アルゴリズムを与える． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2014-AL-149, 号 9, p. 1-6, 発行日 2014-09-05 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
