パス幅を用いた#2SATの厳密アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
2006年にFominらは分枝限定法とパス分解上での動的計画法を組み合わせることによって,いくつかのグラフの問題に対して高速な指数時間厳密アルゴリズムを構成した.本稿では,この手法を#P完全問題のひとつである,重みつき#2SAT問題に対して適用することを考える.まず,パス分解を用いた動的計画法を構成する.そして,各変数の出現回数が少ないときには,既存の分枝限定法を用いたアルゴリズムよりも動的計画法を用いたアルゴリズムの方が高速であることを示した.
- 社団法人電子情報通信学会の論文
- 2007-10-09
著者
関連論文
- ある投票ゲームのシミュレーション
- 単純多角形の生成に関する発見的手法(セッション2)
- 3充足可能性判定問題3SATの単一解を持つ正例題生成手法
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析
- MAX 3SATのランダムな例題生成
- MAX-3SATの解の平均の解析
- Dirichlet分布に従う多項式時間近似サンプリング法(マルコフ連鎖)
- Dirichlet分布のrapidly mixing approximate sampler
- Dirichlet 分布の rapidly mixing approximate sampler
- パス幅を用いた#2SATの厳密アルゴリズム
- MAX 2SATに対するシンプルな正解付テスト例題生成について
- MAX 2SATに対するシンプルな正解付テスト例題生成について
- Test Instance Generation for MAX 2SAT with Fixed Optimal Value (New Aspects of Theoretical Computer Science)
- ある投票ゲームのシミュレーション