DNA計算におけるグラフ三彩色問題への分割統治法の適用について

スポンサーリンク

概要

論文の詳細を見る
Amosらは除去という操作を用いるDNA計算モデルを提唱し,NP-完全問題として知られるいくつかのグラフ問題の解法を示した[2].しかし,その解法は"頂点"の列としてすべての解候補を用意するため,その数は非常に大きくなる.本稿では,Amosらのモデルにおいて,グラフの三彩色問題に対する分割統治法を用いた解法を提案する.そして,シミュレーションをおこない,計算に必要な解候補の数を大幅に削減できることを示す.分割方法については,等分割する場合は,二つに等分割するのが解候補数が抑えられる.さらに,n頂点を1頂点とn-1頂点に分割する場合の方が,解候補数を削減できることがわかった.実行時間に関しては,部分問題を等分割して解く場合はAmosらの方法のO(nlogn)と同じである.しかし,1頂点とn-1頂点に分割する場合については,O(n^21ogn)である.
社団法人電子情報通信学会の論文
2002-09-23

著者

関連論文

もっと見る

スポンサーリンク