最大クリーク問題を解くインスタンスベースのハードウェア解法とFPGAによる実現

摘要

最大クリーク問題はグラフ理論における基本的問題の一つであるが，大規模かつ複雑な問題をソフトウェアで解くと計算時間が膨大になり，実用時間内で解を得ることができない．本研究では，大規模かつ複雑な最大クリーク問題を対象とし，問題のインスタンスに特化したハードウェアをFPGAを用いて実現することにより最大クリーク問題をハードウェアで解くことを目的とする．与えられた問題のインスタンスをハードウェアで解く場合，インスタンスに特化したハードウェアを短時間で構成可能にすると共に，インスタンスの変更に応じて適宜ハードウェアを再構成することが求められる．そこで，再構成可能なLSIであるFPGAを用いることでインスタンスに特化したハードウェアを実現し，最大クリーク問題を短時間で解く手法を提案し，シミュレーション実験により本手法の有効性を示す．