講演抄録/キーワード |
講演名 |
2007-10-16 13:30
パス幅を用いた #2SAT の厳密アルゴリズム ○元木光雄(北陸先端大) COMP2007-43 |
抄録 |
(和) |
2006年に Fomin らは分枝限定法とパス分解上での動的計画法を組み合わせることによって,いくつかのグラフの問題に対して高速な指数時間厳密アルゴリズムを構成した.
本稿では,この手法を \numberP 完全問題のひとつである,重みつき \#2SAT 問題に対して適用することを考える.
まず,パス分解を用いた動的計画法を構成する.
そして,各変数の出現回数が少ないときには,既存の分枝限定法を用いたアルゴリズムよりも動的計画法を用いたアルゴリズムの方が高速であることを示した. |
(英) |
In 2006, Fomin et al. proposed fast exponential-time exact algorithm for some graph problems.
They combined branch-and-reduce technique and dynamic programming over path/tree decomposition.
We are going to apply this technique to satisfiability problem.
We propose a dynamic programming algorithm for counting the number of (maximum weight) satisfying assignment for 2CNF formulas.
Then we show our algorithm is faster than known branch-and-reduce algorithms if maximum degree is small. |
キーワード |
(和) |
動的計画法 / 充足可能性 / 数え上げ問題 / 指数時間厳密アルゴリズム / パス分解 / #P完全 / / |
(英) |
Dynamic programming / Satisfiability / Counting problem / Exponential time exact algorithm / Path decomposition / #P-complete / / |
文献情報 |
信学技報, vol. 107, no. 258, COMP2007-43, pp. 13-17, 2007年10月. |
資料番号 |
COMP2007-43 |
発行日 |
2007-10-09 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-43 |