最小支配集合問題に対する分枝限定アルゴリズムとFPGA上でのハードウェアによる実現

摘要

グラフの最小支配集合問題を解く分枝限定アルゴリズムを提案し、既存の解法との比較を行った．また，提案手法をFPGA上にハードウェアとして実硯し、その惟能をソフトウェアで美瑛した場合と比較した．提案ハードウェア解法では，人ノ」グラフのインスタンスに依存したハードウェア解法の回路記述を自動的に生成し，論理合札配置配線を行った上で回路データをFPGA上にダウンロードして実行する．ソフトウェアで実現した場合と比較した結果，回路生成時間を考慮しても提案手法はソフトウェアより短い計算時問で解を得ることが分かった．